Topic 14 of 20
Topological sort, Union-Find, Dijkstra, Bellman-Ford, Floyd-Warshall and minimum spanning trees.
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.
Cycle detection in a dependency graph; extremely common.
Returning the actual topological order.
Kahn's algorithm on a real-world dependency model.
Peel leaves layer by layer to find the centre.
The first edge that closes a cycle; a Union-Find classic.
Counting components and spare edges.
Merging identities; a frequent Meta and Google question.
Union by row and column keys.
Union the equalities, then check the inequalities.
Shortest path with an edge-count limit.
All-pairs shortest paths on a small graph.
Prim's or Kruskal's on a complete graph.
Minimax path, solvable with a heap or Union-Find.
Hierholzer's algorithm for Eulerian paths.
Finding bridges with discovery and low-link times.
Tests deep understanding of Kruskal's algorithm.