Graph algorithms.
Learn the idea, walk through a graph, then put it into code.
Traversal
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Depth-First Search (DFS) | Easy | O(V + E) | GFG |
| Breadth-First Search (BFS) | Easy | O(V + E) | GFG |
Shortest paths
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Dijkstra’s Algorithm | Medium | O((V + E) log V) | GFG |
| Bellman–Ford Algorithm | Medium | O(V × E) | GFG |
| Floyd–Warshall Algorithm | Medium | O(V³) | GFG |
Ordering
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Topological Sort (Kahn’s Algorithm) | Medium | O(V + E) | GFG |
| Directed Cycle Detection | Medium | O(V + E) | GFG |
Spanning trees
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Prim’s Algorithm | Medium | O((V + E) log V) | GFG |
| Kruskal’s Algorithm | Medium | O(E log E + V) | GFG |
Connectivity
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Disjoint Set Union (Union-Find) | Medium | O(α(V)) amortized / operation | GFG |
| Bipartite Graph Check | Medium | O(V + E) | LeetCode |
| Kosaraju’s Algorithm | Hard | O(V + E) | GFG |
| Tarjan’s SCC Algorithm | Hard | O(V + E) | GFG |
| Bridges in an Undirected Graph | Hard | O(V + E) | LeetCode |
| Articulation Points | Hard | O(V + E) | GFG |