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.