SCC — Kosaraju
Finds strongly connected components with two DFS passes: order nodes by finish time on the graph, then DFS the reversed graph in that order — each tree found is one SCC. Simple to reason about, needs the graph transpose.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
DFS the graph, record finish order reverse every edge DFS the reversed graph, highest finish first each DFS tree = one SCC
Reference implementation
def kosaraju(g):
order = []
dfs_finish_order(g, order)
gr = reverse(g)
for u in reversed(order):
if u not in visited:
comp = dfs_collect(gr, u)