Strongly Connected Components With Kosaraju's Two Passes

One depth-first pass records finishing order; a second, on the reversed graph in reverse finishing order, collects one component per start.

A strongly connected component of a directed graph is a largest group of vertices in which every vertex can reach every other by following edges in their direction, and Kosaraju's algorithm finds all of them with two depth-first searches. The card traces both passes on one graph of seven vertices and explains why the second pass runs on the reversed graph, in an order the first pass sets.

The question comes up whenever reach has to go both ways: which web pages link round to one another, which modules depend on each other in a cycle, which towns can be driven between in both directions on one-way streets. Reaching B from A is not enough; B must reach A too. The graph below has eight edges, A->B, B->A, B->C, C->D, D->E, E->C, E->F and G->F, and each component is drawn as a box.

The topic's directed graph, with its four strongly connected components boxed

The first pass is an ordinary depth-first search over the original graph, started from each unvisited vertex in turn. It records each vertex's finishing time, the moment the search has explored everything reachable from it and backs out. The second pass reverses every edge, then starts a depth-first search from each vertex not yet assigned, taking them in reverse finishing order, latest first. Everything one search of the second pass reaches is one component. The table shows both passes, from a run that visited neighbours in alphabetical order.

Kosaraju's two passes on the topic's graph: where each search starts and what it reaches
Pass	Start vertex	Vertices reached
First, original graph	A	A B C D E F, finishing in the order F E D C B A
First, original graph	G	G alone, since F is already visited; G finishes last
Second, reversed graph	G	G: one component
Second, reversed graph	A	A B: one component
Second, reversed graph	C	C D E: one component; B was skipped as assigned
Second, reversed graph	F	F: one component

The order and the reversal work together. The vertex that finishes last in the first pass always lies in a component that no edge from another component enters: here G, and after G's component is gone, A. Reversing the edges turns such a component into one that no edge leaves, so a search from it on the reversed graph is trapped inside and reaches exactly its own component. G has one edge, G->F, which becomes F->G, so a search from G goes nowhere. A and B are entered by no outside edge, so on the reversed graph they reach only each other. From C the reversed edges lead to B, already assigned, and round the cycle to D and E. Each search of the second pass peels off one component, and the remaining graph again has such a component at the front of the order.

Collapsing each component to a single vertex leaves a directed acyclic graph, here {G} and {A, B} both pointing towards later components and {F} at the end. That condensed graph is what a topological sort can order, which is why components are found first whenever a dependency graph might hold cycles.

Kosaraju's algorithm on a directed graph with V vertices and E edges

Time: O(V + E); two depth-first searches and one pass to reverse the edges
Space: O(V + E); for the reversed graph, plus the visited set and the finishing order
Components: One per search of the second pass; a vertex with no cycle through it is a component on its own

On the Algorithms: Graph Algorithms cheatsheet

← → move through sections and cards