How to Read a Kosaraju Trace
Kosaraju’s algorithm finds the strongly connected components of a directed graph using two depth-first searches. The key to a reliable hand trace is to keep three things separate: the graph used in each pass, the order in which vertices finish in the first pass, and the order in which the second pass starts new searches. A small error in any one of these can merge components that should remain distinct.
All graphs in this tutorial are finite and directed. A directed path from \(u\) to \(v\) follows edge directions from \(u\) to \(v\). Two vertices are strongly connected if each is reachable from the other. Strong connectivity is an equivalence relation, and its equivalence classes are the strongly connected components, or SCCs.
In the trace tables below, a vertex is marked as soon as DFS discovers it. A vertex is finished only after all of its outgoing neighbors in the current graph have been examined. The finishing order is the order of these completion events; decreasing finishing order is that list read backwards. We fix the neighbor order explicitly in each example, since changing it can change the trace even though it does not change the SCCs.
The correctness theorem for Kosaraju’s two-pass algorithm, established in the earlier material on this algorithm, says that for any finite directed graph, these passes produce exactly its SCCs. In particular, the second-pass DFS started at an unassigned vertex collects one whole SCC and no vertices from another. The examples will use this result to check the traces, while the following fact explains why reversing edges does not change which vertices belong together.
Proof. Suppose \(u\) and \(v\) are strongly connected in \(G\). There is a directed path from \(u\) to \(v\) and one from \(v\) to \(u\). Reversing the edges of the first path gives a path from \(v\) to \(u\) in \(G^T\), and reversing the edges of the second gives a path from \(u\) to \(v\) in \(G^T\). Thus they are strongly connected in \(G^T\). The same argument with \(G\) and \(G^T\) exchanged proves the converse: every pair strongly connected in \(G^T\) is strongly connected in \(G\). Therefore the equivalence classes are the same. \(\square\)
Worked Example: Both Passes on One Graph
Worked Example: Recording Finishing Times and SCCs
Let \(G=(V,E)\) be the directed graph with \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{(a,b),(b,a),(b,c),(c,d),(d,c),(d,e),(f,g),(g,f),(g,e)\}\). Use the outgoing-neighbor orders \(a:b\), \(b:a,c\), \(c:d\), \(d:c,e\), \(e:\varnothing\), \(f:g\), \(g:f,e\), and start roots in the order \(a,b,c,d,e,f,g\).
In the first pass, use DFS on \(G\). The stack column lists the active recursive calls after the event. An edge to a gray (currently active) vertex does not start another call.
| Event | Time | Active stack |
|---|---|---|
| Discover \(a\) | 1 | \(a\) |
| From \(a\), discover \(b\) | 2 | \(a,b\) |
| At \(b\), inspect \(b\to a\); \(a\) is active | — | \(a,b\) |
| From \(b\), discover \(c\) | 3 | \(a,b,c\) |
| From \(c\), discover \(d\) | 4 | \(a,b,c,d\) |
| At \(d\), inspect \(d\to c\); \(c\) is active | — | \(a,b,c,d\) |
| From \(d\), discover \(e\) | 5 | \(a,b,c,d,e\) |
| Finish \(e\) | 6 | \(a,b,c,d\) |
| Finish \(d\) | 7 | \(a,b,c\) |
| Finish \(c\) | 8 | \(a,b\) |
| Finish \(b\) | 9 | \(a\) |
| Finish \(a\) | 10 | empty |
| Discover \(f\), then \(g\) | 11, 12 | \(f,g\) |
| At \(g\), inspect \(g\to f\) (active) and \(g\to e\) (finished) | — | \(f,g\) |
| Finish \(g\), then finish \(f\) | 13, 14 | empty |
The increasing finishing order is \(e,d,c,b,a,g,f\). Reverse this list for the second-pass starting order: \(f,g,a,b,c,d,e\). The transpose has outgoing-neighbor lists \(a:b\), \(b:a\), \(c:b,d\), \(d:c\), \(e:d,g\), \(f:g\), and \(g:f\). For example, \((g,e)\) in \(G\) becomes \((e,g)\) in \(G^T\).
| Start in decreasing finish order | What the DFS does in \(G^T\) | New component |
|---|---|---|
| \(f\) | Visit \(g\); its edge to \(f\) returns to the active search. | \(\{f,g\}\) |
| \(g\) | Already assigned. | — |
| \(a\) | Visit \(b\); \(b\to a\) returns to the active search. | \(\{a,b\}\) |
| \(b\) | Already assigned. | — |
| \(c\) | \(c\to b\) reaches an assigned vertex; \(c\to d\) discovers \(d\), and \(d\to c\) returns to the active search. | \(\{c,d\}\) |
| \(d\) | Already assigned. | — |
| \(e\) | Its neighbors \(d\) and \(g\) are already assigned. | \(\{e\}\) |
Check: The output is \(\{f,g\},\{a,b\},\{c,d\},\{e\}\). Within each listed pair, both directions of travel exist: \(a\leftrightarrow b\), \(c\leftrightarrow d\), and \(f\leftrightarrow g\). The only edges between these sets point from \(\{a,b\}\) to \(\{c,d\}\), from \(\{c,d\}\) to \(\{e\}\), or from \(\{f,g\}\) to \(\{e\}\). None point back, so no two of the listed sets can combine into a larger strongly connected component.
Why the Transpose and Order Matter
The first pass is not itself the component assignment. It creates an ordering that guides the second pass. In the example, the first pass finishes the vertices in \(\{a,b\}\) after finishing the vertices in \(\{c,d\}\) and \(e\). Reversing the edges for the second pass prevents a search from following the original outward routes into components that should remain separate. The decreasing finish order ensures the search starts in a component that the transpose cannot carry onward into an unassigned component.
These details give two reliable checks before accepting a hand trace:
- Build \(G^T\) by reversing every edge, without changing the vertex set.
- Use decreasing first-pass finishing time for second-pass roots, and do not start a new search from a vertex already assigned.
The direction of an edge is not an optional convention here. An edge \(u\to v\) means \(u\) can reach \(v\) in \(G\); in \(G^T\), the corresponding edge is \(v\to u\). Reversing only some edges, or using the original graph for the second pass, changes which vertices a search can absorb.
Worked Example: What Goes Wrong with the Original Graph
Worked Example: The Second Pass Uses the Wrong Graph
Use the same explicitly defined graph \(G\), with \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{(a,b),(b,a),(b,c),(c,d),(d,c),(d,e),(f,g),(g,f),(g,e)\}\). The correct decreasing finishing order from the first pass is \(f,g,a,b,c,d,e\). Suppose, incorrectly, that the second pass uses \(G\) rather than \(G^T\).
Start at \(f\). In \(G\), the search follows \(f\to g\), and from \(g\) it follows \(g\to e\). Vertex \(e\) has no outgoing edges. This incorrectly assigns \(\{f,g,e\}\) as one component. Next start at \(a\): the search follows \(a\to b\to c\to d\); the edge \(d\to e\) leads to an already assigned vertex. This incorrectly assigns \(\{a,b,c,d\}\). The remaining roots are already assigned.
Check: The claimed set \(\{f,g,e\}\) is not strongly connected: \(g\) reaches \(e\), but \(e\) has no outgoing edge and so cannot reach \(g\). The claimed set \(\{a,b,c,d\}\) is not strongly connected either: \(b\) reaches \(c\), but there is no directed path from \(c\) or \(d\) back to \(a\) or \(b\). The mistake is not in the first-pass order; it is the use of the wrong graph in the second pass.
Worked Example: What Goes Wrong with Increasing Finish Order
Worked Example: Reversing the Required Order
Again take \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{(a,b),(b,a),(b,c),(c,d),(d,c),(d,e),(f,g),(g,f),(g,e)\}\). Keep the correct transpose \(G^T\), but incorrectly start the second pass in increasing finishing order \(e,d,c,b,a,g,f\).
Starting at \(e\) in \(G^T\), the search follows \(e\to d\), then \(d\to c\), then \(c\to b\), then \(b\to a\). Each vertex is unassigned when first reached, so this single search collects \(\{e,d,c,b,a\}\). The remaining vertices \(g\) and \(f\) are collected together by a later search. The incorrect output is therefore \(\{a,b,c,d,e\}\) and \(\{f,g\}\).
Check: The first claimed set contains vertices from three different true SCCs. In \(G\), \(a\) reaches \(e\), but \(e\) cannot return to \(a\); in \(G^T\), the search from \(e\) can move toward \(a\) because the edges have been reversed. This is exactly why the transpose must be paired with decreasing, not increasing, finishing order.
Worked Example: Disconnected Parts and an Isolated SCC
Worked Example: Restarting After a DFS Tree Ends
Let \(H=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{(1,2),(2,1),(2,3),(4,5)\}\). Use increasing vertex order for roots and the listed order for outgoing neighbors. In the first pass on \(H\), start at \(1\): discover \(1\), then \(2\), then \(3\); finish \(3\), \(2\), \(1\). The next unvisited root is \(4\): discover \(4\), then \(5\); finish \(5\), then \(4\). Thus the decreasing finishing order is \(4,5,1,2,3\).
The transpose has edges \((2,1),(1,2),(3,2),(5,4)\). In the second pass, start at \(4\). It has no outgoing neighbors in \(H^T\), so this search returns \(\{4\}\). The next root \(5\) reaches \(4\), which is already assigned, so it returns \(\{5\}\). Starting at \(1\) reaches \(2\), and \(2\to1\) returns to the active search, giving \(\{1,2\}\). Finally, \(3\to2\) reaches an already assigned vertex, giving \(\{3\}\).
Check: The output is \(\{4\},\{5\},\{1,2\},\{3\}\). Vertices \(1\) and \(2\) reach each other. The edge \(2\to3\) has no return route, and the edge \(4\to5\) has no return route. Vertex \(3\) has no outgoing edge in \(H\). Thus none of these singleton sets can combine with another to form an SCC. This example also shows why both passes must cover every vertex, including vertices in later DFS trees.
Common Mistakes to Catch
A frequent error is to list finishing times correctly but use that list in the wrong direction. If the first pass finishes \(e,d,c,b,a,g,f\), then the second-pass root order is \(f,g,a,b,c,d,e\), not \(e,d,c,b,a,g,f\). Another is to reverse the root order but forget to reverse the edges: both parts of the instruction matter.
It is also important to distinguish a DFS tree from an SCC. A DFS tree records which vertices a search reached using its current edge directions; it is not automatically a strongly connected component. In the wrong-graph example, DFS reaches \(e\) from \(g\), but that one-way reachability does not make \(e\) and \(g\) strongly connected. When a result looks suspicious, check both directions of reachability within each proposed component and inspect whether edges between proposed components can return.
Check Your Understanding
For each question, track the directed edges as written; in a transpose, reverse every edge.
- In the first worked example, what is the first-pass decreasing finishing order, and why is \(f\) before \(g\)?
- For the graph \(V=\{p,q,r\}\), \(E=\{(p,q),(q,p),(q,r)\}\), write the edge set of the transpose.
- Explain why using \(G\) instead of \(G^T\) in the second pass can combine vertices that are connected by a directed path in only one direction.
- Why must the second-pass procedure restart at an unassigned vertex after a DFS finishes?
- In the last example, which edge shows that \(\{1,2\}\) is not strongly connected with \(\{3\}\)? State the missing return path.