Characterizing Strongly Connected Components

We’ll be covering two applications of depth-first search for finding structures that we refer to as the strongly connected components of digraphs. In this lesson, we cover some prerequisite material for these algorithms.

Connectedness in digraphs

The components of a graph embody the essence of connectedness, where every vertex of a component is reachable from every other vertex of that component through some path. In digraphs, the notion of being connected is more nuanced. There could be a path leading from a vertex $v_1$ to a vertex $v_2$, and yet $v_1$ could be unreachable from $v_2$.

See, for example, how there’s a path from $v_1$ to $v_3$ in the following digraph but none from $v_3$ to $v_1$.