The Two-Pass Idea
In a directed graph, one-way reachability does not imply that two vertices belong to the same strongly connected region. Kosaraju’s algorithm finds all such regions with two depth-first searches (DFS): the first pass records when vertices finish, and the second pass searches the graph with every edge reversed. The order from the first pass is essential: it ensures that each second-pass search stays within one component that has not already been found.
All graphs in this tutorial are finite and simple. A directed path from \(u\) to \(v\) is a sequence of vertices starting at \(u\), ending at \(v\), and following directed edges. A vertex is reachable from itself by a path of length zero. Vertices \(u\) and \(v\) are strongly connected if each is reachable from the other. This relation partitions the vertices into strongly connected components (SCCs): maximal sets in which every pair of vertices is strongly connected. A single vertex, including one with no incident edges, is an SCC.
The algorithm uses a fixed order for scanning vertices and outgoing edges, so its trace is reproducible. Any such order is valid. In the first pass, run DFS on \(G\), starting a new search from each vertex not already visited, and record vertices in finishing order. In the second pass, process vertices in the reverse of that order. For each vertex not yet visited in this pass, run DFS in \(G^T\), allowing the search to visit only vertices not already assigned. The vertices reached in that search form one output component.
Visit every vertex with DFS and record each vertex when its search finishes.
The next root is always the unvisited vertex with largest first-pass finishing time.
Start DFS at that root, marking every reached unassigned vertex as one SCC. Continue until all vertices are assigned.
Why Finishing Times Order the Components
Consider the condensation graph: it has one vertex for each SCC, and an edge from one component to another when an original edge goes between them. This graph is acyclic. Indeed, if distinct components lay on a directed cycle in the condensation graph, each would be reachable from each other around that cycle, so they would belong to a single SCC instead.
Proof. Compare the first-discovery times of vertices in \(C\) and \(D\), and consider the component containing the earliest-discovered vertex among the two. Suppose it is \(C\), and let \(x\in C\) be the first vertex discovered in either component. Every vertex of \(C\) is reachable from \(x\) by a directed path within \(C\), and the given edge then makes \(D\) reachable from \(x\). Thus, during the DFS call that discovers \(x\), all vertices of \(D\) are discovered and finished before that call finishes. In particular, \(F(D)<f(x)\leq F(C)\).
Now suppose instead that the earliest-discovered vertex among the two is in \(D\). No vertex of \(D\) can reach \(C\): if one could, the edge from \(C\) to \(D\) would make \(C\) and \(D\) mutually reachable, contradicting that they are distinct SCCs. The DFS call that first discovers a vertex of \(D\) reaches every vertex of \(D\), since they are mutually reachable, but cannot reach \(C\). All vertices of \(D\) therefore finish before any vertex of \(C\) is discovered. Hence \(F(C)>F(D)\) in this case as well. \(\square\)
Applying the lemma along a directed path in the condensation graph shows that if \(D\) can reach a distinct component \(C\), then \(F(D)>F(C)\). This strict order is what prevents a second-pass search from crossing from its root’s component into another unassigned component.
Correctness of the Second Pass
Proof. At the start of a second-pass search, let \(r\) be the unassigned vertex with largest first-pass finishing time, and let \(C\) be its SCC. We prove that the search from \(r\) in \(G^T\), restricted to unassigned vertices, reaches exactly \(C\). We also show that the components already assigned are whole SCCs, which validates this argument at every pass.
First, the search reaches every vertex of \(C\). For any two vertices of \(C\), there are directed paths between them in both directions in \(G\), and reversing the paths gives paths between them in both directions in \(G^T\). In particular, every vertex of \(C\) is reachable from \(r\) in \(G^T\). No vertex of \(C\) has been assigned earlier: inductively, earlier searches have assigned whole SCCs, and \(r\) is still unassigned. So the restricted search can reach all of \(C\).
Next, suppose the search could reach an unassigned vertex in a different SCC \(D\). Then \(G^T\) has a path from \(C\) to \(D\), which means \(G\) has a path from \(D\) to \(C\). By the lemma applied along that path, \(F(D)>F(C)\). But every vertex of \(D\) is unassigned, and \(r\) has largest finishing time among all unassigned vertices. Since \(r\in C\), we have \(F(C)=f(r)\), so \(F(D)>F(C)\) contradicts the choice of \(r\). The search therefore reaches no other unassigned SCC. It finds exactly \(C\).
The initial set of assigned vertices is empty, so the whole-SCC condition holds before the first search. The argument proves it continues to hold after each search. Each search assigns at least its root, and the graph has finitely many vertices, so eventually every vertex is assigned. Each assigned set is an SCC, and every vertex is assigned; consequently, the output is exactly the set of all SCCs. If \(V=\varnothing\), there are no searches and the empty output is correct. \(\square\)
Worked Traces
Worked Example: Three Components in a Directed Chain
Let \(G=(V,E)\) be directed, with \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ba,bc,cd,dc,de,ef,fe\}\). Scan vertices and outgoing neighbors in alphabetical order. The mutual edges give the components \(\{a,b\}\), \(\{c,d\}\), and \(\{e,f\}\), with edges directed from the first component to the second and from the second to the third.
The first DFS starts at \(a\). The table records each entry, return, or edge check; the stack lists the active DFS calls after that action.
| Action | Stack after action | Result |
|---|---|---|
| Enter \(a\), then \(b\) | \([a,b]\) | \(b\) is reached from \(a\) |
| Check \(ba\), then enter \(c\) | \([a,b,c]\) | \(a\) is active; \(c\) is unvisited |
| Enter \(d\) | \([a,b,c,d]\) | \(d\) is reached from \(c\) |
| Check \(dc\), then enter \(e\) | \([a,b,c,d,e]\) | \(c\) is active; \(e\) is unvisited |
| Enter \(f\) | \([a,b,c,d,e,f]\) | \(f\) is reached from \(e\) |
| Finish \(f\), then \(e\) | \([a,b,c,d]\) | Finishing order so far: \(f,e\) |
| Return from \(d\), then finish \(d\) | \([a,b,c]\) | Finishing order: \(f,e,d\) |
| Finish \(c\), then \(b\), then \(a\) | \([]\) | Full finishing order: \(f,e,d,c,b,a\) |
The reverse order is \(a,b,c,d,e,f\). The transpose has edges \(ba,ab,cb,dc,cd,ed,fe,ef\). In particular, the edge \(bc\) has become \(cb\), and \(de\) has become \(ed\).
| Root in reverse order | Unassigned vertices reached in \(G^T\) | Output component |
|---|---|---|
| \(a\) | \(a,b\) | \(\{a,b\}\) |
| \(b\) | Already assigned | Skip |
| \(c\) | \(c,d\) | \(\{c,d\}\) |
| \(d\) | Already assigned | Skip |
| \(e\) | \(e,f\) | \(\{e,f\}\) |
| \(f\) | Already assigned | Skip |
Check: Within each displayed pair, both directed edges are present, so its vertices are mutually reachable. Between the pairs, the original edges go only forward along the chain, so no later pair can reach an earlier one. The three outputs are exactly the SCCs.
Worked Example: A Directed Acyclic Graph
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,34\}\), with directed edges. Use increasing order for vertices and neighbors. The first DFS starts at \(1\), visits \(2\) and finishes it, then visits \(3\), visits and finishes \(4\), and finishes \(3\) and \(1\). Vertex \(5\) is still unvisited, so its separate DFS finishes it. Thus the full finishing order is \(2,4,3,1,5\), and the second-pass order is \(5,1,3,4,2\).
| Second-pass root | Search in \(G^T\), among unassigned vertices | Component found |
|---|---|---|
| \(5\) | No incident edges; search ends at \(5\) | \(\{5\}\) |
| \(1\) | No incoming original edges; search ends at \(1\) | \(\{1\}\) |
| \(3\) | Reaches \(1\), already assigned | \(\{3\}\) |
| \(4\) | Reaches \(3\), already assigned | \(\{4\}\) |
| \(2\) | Reaches \(1\), already assigned | \(\{2\}\) |
Check: There is no directed cycle in this graph. If two distinct vertices were strongly connected, paths in both directions would give a directed cycle. Therefore each vertex is its own SCC, as the five searches report.
Worked Example: Separate Strongly Connected Regions
Let \(V=\{p,q,r,s,t\}\) and \(E=\{pq,qp,rs,sr\}\). Scan in the order \(p,q,r,s,t\). The first DFS from \(p\) visits \(q\), then finishes \(q,p\), giving the order \(q,p\). A new DFS from \(r\) visits \(s\), then finishes \(s,r\). Finally \(t\) finishes by itself. The full finishing order is \(q,p,s,r,t\); the reverse order is \(t,r,s,p,q\).
| Root | Second-pass search in \(G^T\) | Output |
|---|---|---|
| \(t\) | No edges to follow | \(\{t\}\) |
| \(r\) | Visits \(s\), and returns to \(r\) | \(\{r,s\}\) |
| \(s\) | Already assigned | Skip |
| \(p\) | Visits \(q\), and returns to \(p\) | \(\{p,q\}\) |
| \(q\) | Already assigned | Skip |
Check: The pairs \(\{p,q\}\) and \(\{r,s\}\) each have edges in both directions, while \(t\) has no incident edges. There are no edges between these sets, so none can be part of a larger strongly connected set.
Runtime and a Common Pitfall
With adjacency lists, the first DFS examines each vertex and edge a constant number of times. Constructing \(G^T\) takes \(O(|V|+|E|)\) time by scanning the vertices and edges and placing each reversed edge in the appropriate list. The second DFS also examines each vertex and edge a constant number of times. The total running time is therefore \(O(|V|+|E|)\), and the graph storage, transpose, visitation marks, finishing order, and output require \(O(|V|+|E|)\) space.
Pitfall: using the original graph on the second pass. In the first example, the second-pass order begins with \(a\). If the second search is mistakenly run on \(G\) instead of \(G^T\), the search from \(a\) follows \(a\to b\to c\to d\to e\to f\), and incorrectly reports all six vertices as one component. But there is no path from \(f\) back to \(a\), so they are not strongly connected. Reversing every edge changes the search from \(a\) so it reaches only \(a,b\), the correct component.
The algorithm’s two passes have different roles: the first pass establishes the order, while the transpose in the second pass controls which unassigned vertices can be reached. Omitting either feature invalidates the correctness argument. For an empty graph, both passes do nothing and return no components; isolated vertices are each selected as roots and returned as singleton components.
Check Your Understanding
For each question, state the directed edges or reachability facts that support your answer.
- Why does reversing a path in \(G\) give a path in \(G^T\), and what does this imply about reachability within an SCC?
- If an edge goes from SCC \(C\) to a distinct SCC \(D\), which component has the larger maximum finishing time? Explain the two discovery-order cases.
- In the chain example, why can the transpose search from \(c\) reach \(d\) but not the unassigned component \(\{e,f\}\)?
- What incorrect output can result from using \(G\), rather than \(G^T\), in the second pass of the first worked example?
- What does Kosaraju’s algorithm output for a graph with no vertices, and for a graph consisting of one isolated vertex?