Graph Algorithms Beyond Traversal

  • MST: Kruskal / Prim
  • SCC: Kosaraju / Tarjan
  • Bipartite matching: augmenting paths
1 / 4

MST (Kruskal)

  • Sort edges by weight
  • Union if endpoints disconnected
  • O(E log E)
2 / 4

SCC (Kosaraju)

  • DFS to compute finish order
  • Reverse graph DFS in that order
3 / 4

Bipartite matching

  • Alternating paths
  • Hopcroft-Karp for speed
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.