Application 2: Strongly Connected Components

Learn how to split a graph into its 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 GG with three strongly connected components, marked in green, red, and blue, respectively.

Get hands-on with 1200+ tech skills courses.