Strongly Connected Components with Kosaraju
Run DFS on the original graph to get finish-order, transpose the graph, and run DFS again in reverse finish-order to identify SCCs.
Strongly Connected Components Defined
A Strongly Connected Component (SCC) of a directed graph is a maximal set of nodes such that there is a path from every node to every other node within the set. For example, if nodes A, B, C form a cycle (A→B→C→A), they are all in the same SCC. A single node with no self-loop is its own SCC. SCCs reveal the cyclic structure of a directed graph.
Kosaraju's Algorithm: Two DFS Passes
Kosaraju's algorithm finds all SCCs in O(V + E) using two DFS passes. Pass 1: run DFS on the original graph and push nodes to a stack in finishing order (post-order). Pass 2: run DFS on the transposed (reversed) graph, processing nodes in reverse finishing order (pop from stack). Each DFS tree in pass 2 is one SCC.
All lessons in this course
- Kahn's Algorithm: BFS Topological Sort
- DFS Post-Order Topological Sort
- Course Schedule I and II
- Strongly Connected Components with Kosaraju