Graph AlgosGraph Algorithms

Kosaraju's SCC

Find strongly connected components with two DFS passes: record finish order, then DFS the reversed graph in decreasing finish time.

Learn Kosaraju's Algorithm →
ABCDEFGH
Finish order (first → last)
empty
SCCs found
empty
1/33Kosaraju needs two passes. Pass 1 runs DFS on G to compute finishing times; pass 2 runs DFS on the transposed graph in decreasing finish order.
Current nodeOn recursion pathFinished in pass 1 (label = finish rank)SCC (odd)SCC (even)DFS tree edge
PseudocodeLearn Kosaraju's Algorithm →
1order = []; visited = {}
2for u in nodes: if u unvisited: dfs1(u)   # append u to order after its neighbors
3GT = transpose(G)   # reverse every edge
4visited = {}
5for u in reversed(order):
6  if u unvisited in GT: dfs2(u) collects one SCC
7return SCCs
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V + E)
Speed