Strongly Connected Components (Tarjan's Algorithm) already defines the question this page answers: group every node of a directed graph with exactly the other nodes it's mutually reachable with. Tarjan's algorithm answers it in a single DFS pass, threading a discovery-time/low-link pair and an explicit stack through the recursion. Kosaraju's algorithm answers the exact same question a genuinely different way — two full DFS passes, no low-link value anywhere, and one extra piece of preparation: it builds the graph's transpose, every edge reversed. Pass one runs plain DFS on the graph as given and records the order nodes finish in. Pass two runs plain DFS again, this time on the transposed graph, visiting nodes in the reverse of that finish order. Each tree the second pass grows is exactly one strongly connected component.
The same eight intersections and one-way streets as Tarjan's page, for a direct comparison. Press Step or Run to walk both passes: phase 1 explores the graph exactly as drawn, and a node turns solid the moment it finishes — all its neighbors already explored — building the finish-order strip left to right. Once every node has finished, every arrow on the canvas flips: phase 2 runs on the transposed graph, picking the next start node from the right end of the finish-order strip (the last node to finish, first), and grouping everything its DFS tree reaches into one component.
Collapse every SCC down to one node and what's left is the graph's condensation —
a DAG, since any cycle spanning two components would have merged them into one. A DFS forest's
finishing times obey a standing lemma regardless of which graph they're computed on: if an edge in
the condensation runs from component X to component Y, then the highest
finishing time anywhere in X is greater than the highest finishing time anywhere in
Y. Applied to the whole graph, that means whichever single node finishes last
overall must sit in a source component of the condensation — one with no incoming
edges from any other component.
That's exactly the node phase two starts from, and it's why reversing every edge first matters. Reversing the graph reverses the condensation too, so a source component in the original graph becomes a sink — no outgoing edges — in the transpose. Starting a DFS there can still reach every other node in the same component, because mutual reachability within an SCC doesn't care which direction the search runs. But it can't escape to any other component, because in the transpose this component has nowhere else to go. The tree that DFS grows is therefore exactly one full SCC, no more and no less. Marking every node in it as done and repeating — always picking the highest-finishing-time node not yet claimed — peels the condensation's components off one source at a time, and each pass is confined to precisely the nodes still worth exploring.
The demo's own graph makes this concrete. Phase 1 finishes nodes in the order
H, D, F, G, C, E, B, A, so phase 2 tries roots in the reverse:
A, B, E, C, G, F, D, H. The first three of those (B, E) get
swept into A's own component before ever being tried as roots themselves, so the actual
roots used are A, then C, then G, then H —
producing components in exactly the order {A,B,E} → {C,D} → {F,G} → {H}. That's the
condensation's true source-to-sink order, confirmed by checking every edge between components lands
forward, never backward, across 5,000 random graphs. It's also the exact mirror image of Tarjan's own page, which closes
these same four components sink-to-source ({H} first, {A,B,E} last) — two
different algorithms, opposite discovery order, identical grouping.
Matches the demo above one for one — the demo's step generator is this same two-pass shape with
yield points added at each state transition:
function stronglyConnectedComponentsKosaraju(numNodes, adjacency) {
// build the transpose: every edge reversed
const transpose = Array.from({ length: numNodes }, () => []);
for (let u = 0; u < numNodes; u++) {
for (const v of adjacency[u]) transpose[v].push(u);
}
// pass 1: plain DFS on the graph as given, record finish order
const visited = new Array(numNodes).fill(false);
const finishOrder = [];
function dfs1(u) {
visited[u] = true;
for (const v of adjacency[u]) {
if (!visited[v]) dfs1(v);
}
finishOrder.push(u); // pushed on FINISH, not on discovery — see Pitfalls
}
for (let u = 0; u < numNodes; u++) {
if (!visited[u]) dfs1(u);
}
// pass 2: DFS on the TRANSPOSE, roots taken in reverse finish order
const assigned = new Array(numNodes).fill(false);
const sccs = [];
function dfs2(u, component) {
assigned[u] = true;
component.push(u);
for (const v of transpose[u]) {
if (!assigned[v]) dfs2(v, component);
}
}
for (let i = finishOrder.length - 1; i >= 0; i--) {
const u = finishOrder[i];
if (!assigned[u]) {
const component = [];
dfs2(u, component);
sccs.push(component);
}
}
return sccs;
}Forgetting the transpose breaks everything, not just some cases. Running pass two
on the graph as given — instead of on the reversed graph — collapses the demo's four real components
down to one. Checked directly: swap transpose[u] for adjacency[u] in the
loop above and run it against this exact page's graph, and the very first root (A,
highest finish time) reaches every other node through the graph's own forward edges, since
reachability-in-one-direction was never the question phase two is supposed to be confined by. The
result is a single eight-node "component" — {A,B,C,D,E,F,G,H} — silently wrong with no
error of any kind.
The finish-order stack has to hold finish order, not discovery order. It's an
easy slip to push a node the moment dfs1 is called on it, rather than after its whole
subtree has been explored — the difference between one line at the top of the function and one line
at the bottom. Checked directly against this exact page's graph: pushing on discovery instead of
finish still produces four groups, but the wrong four — {A,B,E} and {H}
survive correctly, while {C,D} and {F,G} merge into one incorrect
{C,D,F,G}. The bug is real but partial, which makes it more dangerous than the
no-transpose bug above: two of four components look right, so a spot check on the wrong pair would
miss it entirely.
Two full passes cost more than Tarjan's one, even at the same O(V + E). Kosaraju's needs the transpose adjacency built and stored (roughly doubling the edge memory), then two complete DFS traversals instead of one. The asymptotic bound is identical, but the constant factor isn't — pick Tarjan's algorithm when that matters, or Kosaraju's when the simplicity of "plain DFS, twice, no low-link bookkeeping" is worth more than the constant.
Same deep-recursion limit as any DFS. Both passes here are recursive, so a long enough chain of nodes can overflow the call stack exactly as DFS's own Pitfalls and Tarjan's Pitfalls both describe — an iterative rewrite with an explicit stack applies to each pass here the same way.
Time: O(V + E) — building the transpose is one pass over every edge,
and each DFS pass visits every vertex and inspects every edge once. Three linear passes summed is
still linear. Space: O(V + E) — the transpose adjacency list is the one
real addition over Tarjan's O(V), which never needs to store a second copy of the
graph.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.