Finding Connected Components in Graphs

Connected Components

A connected component is a maximal set of vertices such that every vertex in the set can reach every other vertex through some path. Understanding components reveals the structure and clusters within a graph.

Undirected Graphs

In an undirected graph, finding connected components is straightforward:

1. Start DFS/BFS from an unvisited node
2. All nodes reached belong to the same component
3. Repeat from the next unvisited node
4. Continue until all nodes are visited

Graph: A-B, C-D, E (isolated)
Components: {A,B}, {C,D}, {E}

Directed Graphs: Strongly Connected Components (SCCs)

In a directed graph, a strongly connected component is a maximal set where every node can reach every other node following edge directions. Two classical algorithms find SCCs:

Kosaraju's Algorithm:

1. Run DFS and record finish times
2. Transpose the graph (reverse all edges)
3. Run DFS on the transposed graph in reverse finish-time order
4. Each DFS tree in step 3 is an SCC

Tarjan's Algorithm:

• Uses a single DFS pass with a stack
• Tracks discovery time and the lowest reachable ancestor
• When a node's low-link equals its discovery time, pop the stack to form an SCC

Time Complexity

All component-finding algorithms run in O(V + E).

Applications

• Network reliability — Components reveal how many separate subnetworks exist
• Social clusters — Identify communities within social networks
• Graph condensation — Replace each SCC with a single node to form a DAG