Strong Connectivity

Understand the different techniques used to implement strong connectivity efficiently.

Let’s go back to the proper definition of connectivity in directed graphs. Recall that one vertex uu can reach another vertex vv in a directed graph GG if GG contains a directed path from uu to vv, and that reach(u)reach(u) denotes the set of all vertices that uu can reach. Two vertices uu and vv are strongly connected if uu can reach vv and vv can reach uu. A directed graph is strongly connected if, and only if, every pair of vertices is strongly connected.

Tedious definition-chasing implies that strong connectivity is an equivalence relation over the set of vertices of any directed graph, just like connectivity in undirected graphs. The equivalence classes of this relation are called the strongly connected components or, more simply, the strong components of GG. Equivalently, a strong component of GG is a maximal strongly connected subgraph of GG. A directed graph GG is strongly connected if, and only if, GG has exactly one strong component; at the other extreme, GG is a dag if, and only if, every strong component of GG consists of a single vertex.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy