12.5 Strongly connected components

In Module 12.2, a directed route from $A$ to $B$ did not guarantee a route back. Now ask a stronger question: which vertices can reach one another in both directions? If $A$ can reach $B$ and $B$ can reach $A$, they can communicate through the network even if they have no direct two-way edge. If $B$ and $C$ can also reach one another, joining those routes shows that $A$ and $C$ can reach one another too. This lets us group vertices by mutual reachability.

A strongly connected component (SCC) is one of these groups, extended as far as possible: every vertex in it can reach every other, and no additional vertex can join while that remains true. We use SCCs to compress a complicated network of cycles into a simpler map of one-way movement between groups. In a task-dependency graph, a component containing a cycle exposes a circular dependency. The compressed map also reveals sink components, which have no outgoing edge to another group. A process following edges can enter such a component but cannot leave it; that matters for state transitions and the random walks in Module 12.6.

This is intermediate graph theory. Review reachability and DFS first. The Johns Hopkins SCC lecture notes give a full algorithmic treatment.

A basic idea: mutual reachability makes a group

Suppose $A\to B$, $B\to A$, $B\to C$, $C\to D$, $D\to C$, and $D\to E$. First check return routes: $A$ and $B$ reach each other, and $C$ and $D$ reach each other. The arrow $B\to C$ lets the first pair reach the second, but there is no route from $C$ back to $B$, so the pairs cannot be one SCC. Vertex $E$ has no way back to the others and forms a component by itself. The three groups are $\{A,B\}$, $\{C,D\}$, and $\{E\}$.

A quick tour of components and sinks

Maximal means that we cannot add another vertex to the group while keeping mutual reachability; it does not mean that the component has more vertices than every other component. Each vertex belongs to exactly one SCC. A single vertex is an SCC even without a self-loop, because a zero-length path reaches itself. An edge inside an SCC is allowed; a sink SCC only forbids edges leaving for a different SCC.

Compress every SCC into one node, keeping arrows between different components. This condensation graph has no directed cycle: if a cycle joined several components, each could reach the others and they would actually be one SCC. Therefore the condensation graph is a directed acyclic graph. A finite nonempty condensation graph has at least one sink.

For a small graph, trace reachability in both directions, group mutually reachable vertices, then scan outgoing edges from each group. For a large graph, Kosaraju's algorithm uses two DFS passes:

1. DFS the original graph and record vertices when their searches finish.
2. Reverse every edge.
3. DFS the reversed graph in decreasing order of first-pass finishing time. Each new search marks one SCC.

The finishing order and reversal prevent a second-pass search from mixing components linked only one way. With adjacency lists, the two passes take $O(|V|+|E|)$ time. The small-graph grouping method is enough to answer most hand questions; the two-pass algorithm makes the same task efficient on large graphs.

Application 1: web pages that link one way

Pages have links $A\leftrightarrow B$, $B\to C$, $C\leftrightarrow D$, and $D\to E$. Find the SCCs and sink SCCs.

1. Find mutual groups. $A,B$ reach each other; $C,D$ reach each other; $E$ stands alone. The SCCs are $\{A,B\}$, $\{C,D\}$, $\{E\}$.
2. Compress. The component arrows are $\{A,B\}\to\{C,D\}\to\{E\}$.
3. Identify sinks. Only $\{E\}$ has no arrow to another component, so it is the sole sink SCC.

Application 2: two possible terminal groups

A process has states $S,A,B,C$ and moves $S\to A$, $S\to B$, $A\to A$, $B\to C$, and $C\to B$. Which components can trap a path once entered?

1. Group mutual reachability. The SCCs are $\{S\}$, $\{A\}$, and $\{B,C\}$.
2. Check outgoing edges. $\{S\}$ points to both other groups. Neither $\{A\}$ nor $\{B,C\}$ points out.
3. Conclude. Both $\{A\}$ and $\{B,C\}$ are sink SCCs. A path entering either cannot reach the other under these moves.

The two sinks explain why a process without added moves may have different long-run outcomes depending on its route.