Pattern visualizer
Strongly Connected Components (Kosaraju's)
A component is a set of nodes that can all reach each other, so the hard part is telling 'reaches' apart from 'reaches AND is reached by'. Kosaraju's trick: run one DFS on the graph and record the order nodes FINISH in — a node finishes only after everything it can reach has already finished, so the last node to finish can reach no unfinished node above it in that order. Then reverse every edge and DFS again, popping nodes in that finish order. On the reversed graph, an edge that used to let a node escape its component now points back in, so each DFS from an unclaimed node can only sweep up its own component before running out of places to go. Animated on: 5 nodes, edges 0->1, 1->2, 2->0, 1->3, 3->4 — find every strongly connected component..
Two DFS passes: finish order on the graph, then components on its reverse
Directed graph
5 nodes, 5 directed edges. A strongly connected component is a set of nodes that can all reach each other — 0, 1 and 2 form a cycle here, so any two of them can reach one another, while 3 and 4 only ever get reached, never reach back.
1FUNCTION stronglyConnected(n, edges):2 adj, radj <- BUILD adjacency lists FROM edges AND reversed edges3 finishOrder <- empty stack4 FOR v FROM 0 TO n - 15 IF NOT visited1[v]6 DFS1(v, adj) THEN PUSH v TO finishOrder7 visited2 <- FALSE for every node8 components <- empty list9 WHILE finishOrder NOT EMPTY10 v <- POP finishOrder11 IF NOT visited2[v]12 component <- DFS2(v, radj)13 APPEND component TO components14 RETURN components
← / → step · space play · Home restart