Course contentsShow
← Mathematics
Lesson 2664 of 3,12153. Graph TheoryFree lesson

Strongly Connected Digraphs

Define strong connectivity in directed graphs; identify strongly connected components using path existence.

Strongly Connected Digraphs

What you'll learn: You'll discover what it means for a directed graph to be strongly connected and how to identify its strongly connected components.

What is Strong Connectivity?

In a directed graph (digraph), edges have direction—they go from one vertex to another. A digraph is strongly connected if there's a directed path from every vertex to every other vertex. In other words, you can travel from any vertex to any other vertex by following the arrows.

Think of it like a city's one-way street system: the city is strongly connected if you can drive from any location to any other location while obeying all the one-way signs. If some location is unreachable from another, the system isn't strongly connected.

Strongly Connected Components

Not every digraph is strongly connected overall, but we can partition its vertices into strongly connected components (SCCs)—maximal subsets where every pair of vertices within that subset can reach each other via directed paths.

For example, imagine a social network where an edge from A to B means "A follows B." An SCC would be a group where everyone follows everyone else (possibly through intermediaries), but no one outside the group has this mutual reachability with everyone inside.

Identifying Strong Connectivity

To check if a digraph is strongly connected:

  1. Pick any vertex v
  2. Verify that v can reach all other vertices via directed paths
  3. Verify that all other vertices can reach v

If both conditions hold for one vertex, the entire graph is strongly connected. To find all SCCs in a larger graph, you'd systematically identify maximal groups satisfying the mutual reachability property.

Key Takeaway: A digraph is strongly connected when every vertex can reach every other vertex through directed paths; strongly connected components partition the graph into maximal mutually reachable subsets.