Chapter 14 · Advanced Graphs
Strongly Connected Components (SCC)
Group the vertices of a directed graph so that inside a group everyone can reach everyone. Kosaraju does it with two Depth-First Search (DFS) passes; Tarjan does it in one pass with low-link values. Collapse each group and a Directed Acyclic Graph (DAG) appears.
Click a vertex, then another, to add or remove that directed edge.
current vertex
on the DFS path (in progress)
finished, no component yet
DFS tree edge
edge being examined
🎨 other fills = one color per component
Condensation DAG (each component collapsed to one node)
How to read this
- Kosaraju. Pass 1 runs DFS on the graph and writes each vertex into the finish order strip when its DFS call ends (the small
f=number). Then every arrow flips (the transpose). Pass 2 takes vertices from the end of the finish order; each DFS on the flipped graph paints exactly one component. - Tarjan. Each vertex shows
idx/low: its discovery number and the smallest discovery number it can reach through its DFS subtree plus one edge back to a vertex still on the stack. The stack strip shows vertices not yet assigned. When a vertex finishes withlow = idxit is the root of a component: pop down to it. - Dashed gray edges are ignored: they lead into a component that is already finished.
- The condensation below draws one node per component with an arrow wherever some edge crosses between two components. It never has a cycle: if two components could reach each other, they would be one component.
- Counters: both algorithms visit each vertex and examine each edge a constant number of times: O(V + E).
Try this
- Lesson graph, Kosaraju: the finish order is
5 4 3 2 1 0 7 6. Pass 2 starts at 6 and finds {6, 7}, then {0, 1, 2}, then {3, 4, 5}. - Same graph, Tarjan: final
lowvalues are 0 0 0 3 3 3 6 6, and components come out as {3, 4, 5}, {0, 1, 2}, {6, 7}, which is reverse topological order of the condensation. - Click 5 then 1 to add edge 5 → 1. Now 0…5 all reach each other: two components merge into one, and the condensation shrinks.
- Press A DAG: every vertex is its own component, and Kosaraju's pass-2 order is a topological order.
- Kosaraju: what goes wrong if pass 2 used the original graph? Try it in your head on the lesson graph: a DFS from 6 would leak into {3, 4, 5}. That's why the transpose matters.