Module 37
Advanced Graph Algorithms
Strongly connected components, bridges and articulation points, bipartite checks, Euler paths, maximum flow and A* search.
The core graph modules answered reachability, ordering and shortest paths. This module covers the structural questions that come up in harder interviews and real systems: which nodes form mutually reachable groups, which single link or server would split a network, whether a graph can be two-coloured, how to use every edge exactly once, how much can flow from a source to a sink, and how a good heuristic speeds up shortest-path search.
Most of these build on one idea: DFS discovery times plus the "lowest reachable discovery time" (low-link) of each subtree.
Best after: Depth-First Search, Shortest Paths
Where this shows up in real systems
- System Design · Topic 14.10 — Limiting Blast Radius: Cells, Shuffle Sharding & Regions — A bridge or articulation point in the dependency graph is a single point of failure.
Part 1
Learn the ideas
- 37.1Bridges and Articulation Points (Low-Link)During DFS, low[u] is the smallest discovery time reachable from u's subtree using at most one back edge. An edge u–v is a bridge when low[v] > disc[u].16 min
- 37.2Strongly Connected ComponentsIn a directed graph, an SCC is a maximal set where every node reaches every other. Kosaraju finds them with two DFS passes; Tarjan with one pass and low-links.14 min
- 37.3Bipartite Graphs, Euler Paths and Maximum FlowTwo-colour a graph with BFS; walk every edge once with Hierholzer's algorithm; push the most flow from s to t with augmenting paths.16 min
Part 2
Solve the problems
Work through them in order. Each one shows the pattern it teaches.
Tarjan's bridge-finding with disc and low arrays.
The node version of low-link: a child that can't climb above its parent.
Kosaraju's two passes.
Two-colouring with BFS, checking every component.
Hierholzer's algorithm: post-order over consumed edges gives an Euler path.
Edmonds-Karp: BFS augmenting paths in the residual graph.
Search over board states: BFS, or A* with a Manhattan-distance heuristic.