Graph (DFS, BFS)

Graph

Basics

• Directed Acyclic Graph (DAG): directed graph which does not contain any cycles

Graph Traverse

Depth Fisrt Search (DFS)

Breadth Fisrt Search (BFS)

Topological Sort (TS)

• For a directed graph G = (V, E), a topological order is an assignment o: V → N such that for all (u, v) ∈ E, we have o(u) < o(v).
• Topological order exists if and only if graph is acyclic, i.e. DAG

Algorithm

Implementation using DFS

Strongly Connected Component(SCC) Discovery

Algorithm

1. Tarjan’s SCC Discovery
2. Using DFS

Minimum Spanning Tree

Source: Geeks for Geeks

• A minimum spanning tree connects all the vertices in the graph, ensuring that there is a path between any pair of nodes.

Spanning Tree

• Spanning trees only exist for connected graphs, otherwise a spanning tree exists for each connected component.
• All spanning trees of a graph have the same number of edges.

Visualization

• https://visualgo.net/en/mst?slide=1

Kruskal’s algorithm

Visualization

• https://www.cs.usfca.edu/~galles/visualization/Kruskal.html

Prim’s algorithm

Visualization

• https://www.cs.usfca.edu/~galles/visualization/Prim.html

• https://algorithms.discrete.ma.tum.de/graph-algorithms/mst-prim/index_en.html

Reference

DFS

• https://www.geeksforgeeks.org/dsa/difference-between-bfs-and-dfs/

TS

• https://www.geeksforgeeks.org/dsa/topological-sorting/
• https://www.geeksforgeeks.org/dsa/introduction-to-directed-acyclic-graph/

SCC

• https://www.geeksforgeeks.org/dsa/tarjan-algorithm-find-strongly-connected-components/

Minimal Spanning Tree (MST)

• https://www.geeksforgeeks.org/dsa/spanning-tree/
• https://algorithms.discrete.ma.tum.de/graph-algorithms/mst-prim/index_en.html