Card 07/ 07
Recap: Graph Connectivity
Two passes find mutual reach, low values find weak links, and the wording of the question picks the tool.
Graph connectivity asks how a graph holds together, and the topic taught two algorithms that answer the questions a plain traversal cannot, and a rule for choosing among four tools. The table below lists each idea with the card that taught it.
| The idea | Where |
|---|---|
| Strongly connected components, found by finishing order, then a search of the reversed graph from each unassigned vertex | Strongly Connected Components With Kosaraju's Two Passes |
| Without the reversal, a search flows out of its component and merges the next | Running Kosaraju's Second Pass on the Original Graph |
| Discovery times and low values; a bridge when low[child] > disc[parent], an articulation point when low[child] ≥ disc[parent], the root with two children | Bridges and Articulation Points From Discovery Times and Low Values |
| Skip the parent edge, judge the root by its children, and keep an explicit stack for deep graphs | Bridges and Articulation Points in Python, Java and TypeScript |
| Union-find for arriving edges, a traversal for fixed reach, components for mutual reach, bridges for single failures | Union-Find vs Traversal vs Components vs Bridges |
| Choose the tool for each question, then run it on a new network | Practice: Finding Weak Links in a Delivery Network |
Both algorithms are one or two depth-first searches with a little bookkeeping, and both run in O(V + E). Kosaraju's algorithm uses the order in which the first search finishes to pick where the second should start, and the reversed edges to keep each search inside one component. The low-value search uses the time each vertex was discovered to ask whether a subtree has a way back above its parent that avoids the edge it hangs from.
The four tools look alike because each groups vertices by reach. The question tells them apart: whether edges keep arriving, whether they have a direction, and whether it asks who is connected or what one failure would break.
Graph Connectivity is the last topic of Algorithms. The subject opened on measuring how running time grows and closes on graphs, and every algorithm along the way, from a sort to a shortest path, was chosen the same way: by naming what the problem asks and what the input allows.
← → move through sections and cards