Application 2: Strongly Connected Components

In this lesson, we use graph traversal to separate a directed graph into its strongly connected components. Such a decomposition can reveal useful information on the graph structure and can be the first step for more involved graph algorithms.

Strongly connected components

Recall that a directed graph is called strongly connected when any pair of nodes can reach each other. Even if the whole graph is not strongly connected, it can be split up into parts called its strongly connected components (SCCs).

The following illustration shows a graph $G$ with three strongly connected components, marked in green, red, and blue, respectively.

For example, the nodes $0$ and $4$ are in the same SCC, as we can reach node $0$ from node $4$ and also reach node $4$ from node $0$ (via node $6$). On the other hand, nodes $4$ and $5$ are in distinct SCCs: although we can go from node $4$ to node $5$, there is no way to go from node $5$ to node $4$.

After identifying strongly connected components in a graph $G = (V, E)$, we can contract them to form a new graph $G'$, called the contracted component graph of $G$. The nodes of the contracted component graph are the SCCs of $G$. There is an edge between SCCs $X$ and $Y$ ...