Skip to content

Topic 14 of 20

Advanced Graphs

Topological sort, Union-Find, Dijkstra, Bellman-Ford, Floyd-Warshall and minimum spanning trees.

20 problems0 Easy14 Medium6 Hard

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

  1. 1

    Cycle detection in a dependency graph; extremely common.

    Topological Sort (Kahn / DFS)Reported at: AmazonMicrosoftMeta+6
  2. 2

    Returning the actual topological order.

    Topological Sort (Kahn / DFS)Reported at: AmazonGoogleMicrosoft+6
  3. 3

    Kahn's algorithm on a real-world dependency model.

  4. 4

    Peel leaves layer by layer to find the centre.

    Topological TrimmingReported at: AmazonSnap
  5. 5

    The first edge that closes a cycle; a Union-Find classic.

    Union-Find (Disjoint Set Union)Reported at: GoogleMicrosoft
  6. 6
  7. 7

    Merging identities; a frequent Meta and Google question.

    Union-Find (Disjoint Set Union)Reported at: MetaAppleGoogle+3
  8. 8
  9. 9

    Union the equalities, then check the inequalities.

  10. 10

    The textbook Dijkstra problem.

    DijkstraReported at: GoogleAmazon
  11. 11

    Dijkstra minimising the maximum edge along a path.

  12. 12

    Shortest path with an edge-count limit.

  13. 13
  14. 14

    Prim's or Kruskal's on a complete graph.

  15. 15

    Minimax path, solvable with a heap or Union-Find.

  16. 16

    Longest path in a DAG with a topological order.

  17. 17
  18. 18

    Hierholzer's algorithm for Eulerian paths.

    Eulerian Path (Hierholzer)Reported at: MetaGoogleAmazon+3
  19. 19

    Finding bridges with discovery and low-link times.

  20. 20