function kosaraju(graph: Graph) {const order: Node[] = []; const seen = new Set<Node>();
const finish = (node: Node) => { seen.add(node); for (const next of graph.successors(node)) if (!seen.has(next)) finish(next); order.push(node); };for (const node of graph.nodes) if (!seen.has(node)) finish(node);
const reversed = graph.reverse();
const components: Node[][] = []; seen.clear();
const collect = (node: Node, component: Node[]) => { seen.add(node); component.push(node); for (const next of reversed.successors(node)) if (!seen.has(next)) collect(next, component); }; for (const node of order.reverse()) {if (seen.has(node)) continue;
const component: Node[] = []; collect(node, component);
components.push(component);
}
return components;
}
A is unvisited: depth-first search from there, recording when each node finishes.
Understanding Kosaraju
The idea
Kosaraju's algorithm needs two depth-first searches. The first runs on the graph and records the order in which nodes finish. The second runs on the reversed graph, starting from the nodes that finished last, and every tree it grows is exactly one strongly connected component.
It works because the last node to finish lies in a source component of the condensation, and in the reversed graph a source becomes a sink: the search from it cannot escape its own component. Then the next unvisited latest finisher, and so on. Twice the work of Tarjan, but each pass is a plain DFS.
The four stages
Complexity
Versus its siblings
Pseudocode
KOSARAJU(graph)
first pass: DFS the graph; append each node to `order` when it finishes
reverse every edge
second pass: for each node in decreasing finish order, if unvisited
DFS on the reversed graph from it; every node reached is one component
When to use
Pitfalls
History
S. Rao Kosaraju described the two-pass method in unpublished lecture notes in 1978; Micha Sharir published it independently in 1981. It is the algorithm most textbooks teach first because its proof fits on a page, even though Tarjan's single pass from 1972 is faster.