Topic 14 of 20
Advanced Graphs
Topological sort, Union-Find, Dijkstra, Bellman-Ford, Floyd-Warshall and minimum spanning trees.
The concept
Once plain BFS and DFS feel natural, a handful of named algorithms unlock the remaining graph questions. Topological sort orders the nodes of a directed acyclic graph so every edge points forward. Use it for course prerequisites, build systems and anything with dependencies; Kahn's algorithm (BFS on in-degrees) also detects cycles. Union-Find (disjoint set union) merges groups and answers "are these connected?" in almost O(1) with path compression and union by rank.
For weighted shortest paths, Dijkstra's algorithm (a min-heap of tentative distances) handles non-negative weights in O(E log V). Bellman-Ford handles negative weights or a limit on the number of edges, and Floyd-Warshall gives all-pairs distances on small graphs. A minimum spanning tree connects every node at the lowest total cost, with Prim's (heap-based) or Kruskal's (sort edges plus Union-Find).
Learn each algorithm's template well enough to write it from memory. Interviewers rarely ask you to invent these; they want to see you recognise which one applies and implement it cleanly.
Patterns you will learn
Problems, in order
- 1Course ScheduleMedium
Cycle detection in a dependency graph; extremely common.
Topological Sort (Kahn / DFS)Reported at: AmazonMicrosoftMeta+6 - 2Course Schedule IIMedium
Returning the actual topological order.
Topological Sort (Kahn / DFS)Reported at: AmazonGoogleMicrosoft+6 - 3
Kahn's algorithm on a real-world dependency model.
- 4Minimum Height TreesMedium
Peel leaves layer by layer to find the centre.
Topological TrimmingReported at: AmazonSnap - 5Redundant ConnectionMedium
The first edge that closes a cycle; a Union-Find classic.
Union-Find (Disjoint Set Union)Reported at: GoogleMicrosoft - 6
Counting components and spare edges.
- 7Accounts MergeMedium
Merging identities; a frequent Meta and Google question.
Union-Find (Disjoint Set Union)Reported at: MetaAppleGoogle+3 - 8
Union by row and column keys.
- 9
Union the equalities, then check the inequalities.
- 10
- 11
- 12
Shortest path with an edge-count limit.
- 13
All-pairs shortest paths on a small graph.
- 14
Prim's or Kruskal's on a complete graph.
- 15
Minimax path, solvable with a heap or Union-Find.
- 16
- 17
- 18
Hierholzer's algorithm for Eulerian paths.
Eulerian Path (Hierholzer)Reported at: MetaGoogleAmazon+3 - 19
Finding bridges with discovery and low-link times.
- 20
Tests deep understanding of Kruskal's algorithm.