Finding Strongly Connected Components

Graph Theory · Axiom Academy

LESSON Finding Strongly Connected Components Algorithms for discovering SCCs: Kosaraju's two-pass approach and Tarjan's single-pass method 1. SCCs Partition the Vertices A crucial property of strongly connected components is that they form a partition of the vertex set. This means: Every vertex belongs to exactly one SCC SCCs are disjoint - no vertex belongs to multiple SCCs SCCs are maximal - you cannot add more vertices while maintaining strong connectivity This partition property is fundamental to both SCC algorithms, as it guarantees that we can independently identify each component without overlap. 2. The Condensation Graph (DAG) Once we identify all SCCs, we can construct the condensation graph (also called the component graph) where: Each node represents one SCC from the original graph There is an edge from SCC A to SCC B if there exists at least one edge in the original graph from a vertex in A to a vertex in B The DAG structure of the condensation graph enables efficient analysis of dependencies and hierarchical relationships in the original directed graph. 3. Kosaraju's Algorithm (Two DFS Passes) Kosaraju's algorithm finds all SCCs using two depth-first searches: one on the original graph and one on the transpose graph. First Pass: Run DFS on the original graph G to compute finish times for all vertices. Store vertices in decreasing order of finish time. Transpose: Compute G^T (reverse all edge directions).

This is the written version of the interactive lesson above. See the full Graph Theory course.