Mutual Reachability in a Digraph
In a directed graph, following an arc from \(u\) to \(v\) does not imply that there is a route back from \(v\) to \(u\). Strong connectivity captures the stronger condition: every vertex can reach every other vertex by following the directions of the arcs. When a digraph is not strongly connected as a whole, its vertices still divide into maximal groups within which travel is possible in both directions. These groups are its strongly connected components.
Throughout, a digraph \(D=(V,A)\) is finite and has no loops or multiple arcs unless stated otherwise. An arc from \(u\) to \(v\) is written \((u,v)\). A directed walk is a sequence \(v_0,v_1,\dots,v_\ell\) such that \((v_{i-1},v_i)\in A\) for each \(i\). A directed path is a directed walk with no repeated vertices; we allow a path of length zero from a vertex to itself. We say \(u\) reaches \(v\) if there is a directed path from \(u\) to \(v\).
For reachability, it makes no difference whether we first allow directed walks or require directed paths. If a directed walk repeats a vertex, the portion between two occurrences of that vertex can be deleted, leaving a shorter directed walk with the same endpoints. Repeating this deletion eventually gives a path. Thus concatenating directed paths gives a walk, and that walk can be reduced to a path.
In the definition of a component, maximal means that no additional vertex can be included while keeping every pair mutually reachable. The components are sets of vertices, not merely selected collections of arcs: the arcs induced by each component are considered when describing its internal connectivity.
Why the Components Partition the Vertices
Proof. We check the three properties. For every vertex \(u\), the length-zero path shows that \(u\) reaches itself, so \(u\) is mutually reachable with itself. If \(u\) is mutually reachable with \(v\), then \(u\) reaches \(v\) and \(v\) reaches \(u\); reversing the order of these two statements shows that \(v\) is mutually reachable with \(u\). Finally, suppose \(u\) is mutually reachable with \(v\), and \(v\) is mutually reachable with \(w\). There is a directed path from \(u\) to \(v\) and one from \(v\) to \(w\). Concatenating them gives a directed walk from \(u\) to \(w\), which reduces to a directed path. The paths from \(w\) to \(v\) and \(v\) to \(u\) give a directed path from \(w\) to \(u\) in the same way. Hence \(u\) and \(w\) are mutually reachable. This proves transitivity. An equivalence relation partitions a set into disjoint equivalence classes; each class is pairwise mutually reachable, and any pairwise mutually reachable set is contained in one class. Therefore the classes are precisely the maximal such sets. \(\square\)
Proof. Let \(u,v\in C\). Since \(C\) is an equivalence class, there are paths from \(u\) to \(v\) and from \(v\) to \(u\). Consider a vertex \(x\) on the path from \(u\) to \(v\). The initial part of that path shows that \(u\) reaches \(x\). The remaining part, followed by a path from \(v\) back to \(u\), shows that \(x\) reaches \(u\). Thus \(x\) is mutually reachable with \(u\), so \(x\in C\). The path from \(u\) to \(v\) therefore stays inside \(C\); the same argument applies to the path from \(v\) to \(u\). These paths lie in the induced subdigraph on \(C\), proving it is strongly connected. Now let \(H\) be a strongly connected subdigraph. For any two vertices of \(H\), strong connectivity supplies paths in both directions in \(H\), hence in \(D\). Those vertices are mutually reachable in \(D\), so they belong to the same equivalence class. Thus all vertices of \(H\) lie in a single component. \(\square\)
Finding Components by Searches
A direct method is to search from each vertex and record which vertices it reaches. Let \(R(u)\) denote the set of vertices reachable from \(u\). Then two vertices belong to the same component exactly when each lies in the other’s reachability set:
To find \(R(u)\), start with \(u\) marked and place it in a queue. Repeatedly remove a vertex from the queue and add each of its unmarked out-neighbors to the queue. Stop when the queue is empty. The search is valid because every newly marked vertex is reached along an arc from a vertex already reached. Conversely, if a vertex is reachable, consider a path to it: each successive vertex on that path is marked when the preceding vertex is processed. Thus, when the search ends, precisely the reachable vertices have been marked.
For a finite digraph, this procedure terminates: each vertex is added to the queue at most once. Running it from every vertex gives all sets \(R(u)\); testing the displayed condition then groups vertices into components. The examples trace the queue explicitly. A queue is written from front to back, and an empty queue is \([]\).
Worked Example: Two Components with Arcs Between Them
Let \(D=(V,A)\), where \(V=\{a,b,c,d,e\}\) and \(A=\{(a,b),(b,a),(b,c),(c,b),(c,d),(d,e),(e,d)\}\). Find the strongly connected components.
Run the queue search from each vertex. The queue sequences below show the queue after each removal and after adding newly discovered out-neighbors:
| Start | Queue changes | Reachable set |
|---|---|---|
| \(a\) | \([a]\to[b]\to[c]\to[d]\to[e]\to[]\) | \(R(a)=\{a,b,c,d,e\}\) |
| \(b\) | \([b]\to[a,c]\to[c]\to[d]\to[e]\to[]\) | \(R(b)=\{a,b,c,d,e\}\) |
| \(c\) | \([c]\to[b,d]\to[d,a]\to[a,e]\to[e]\to[]\) | \(R(c)=\{a,b,c,d,e\}\) |
| \(d\) | \([d]\to[e]\to[]\) | \(R(d)=\{d,e\}\) |
| \(e\) | \([e]\to[d]\to[]\) | \(R(e)=\{d,e\}\) |
For example, from \(c\), processing \(c\) discovers \(b\) and \(d\); processing \(b\) discovers \(a\); processing \(d\) discovers \(e\). The remaining vertices have no unmarked out-neighbors. The reachability sets show that \(a,b,c\) reach one another in both directions, and \(d,e\) do as well. Although \(a,b,c\) can reach \(d,e\), neither \(d\) nor \(e\) can reach \(a,b,c\). Hence the components are \(\{a,b,c\}\) and \(\{d,e\}\).
Check: The first set is strongly connected using the arcs \(a\to b\), \(b\to a\), \(b\to c\), and \(c\to b\); the second is strongly connected using \(d\to e\) and \(e\to d\). No component can include vertices from both sets because there is no directed path from either \(d\) or \(e\) back to \(a\), \(b\), or \(c\).
Worked Example: One-Way Reachability Does Not Merge Components
Let \(D=(V,A)\), where \(V=\{1,2,3,4\}\) and \(A=\{(1,2),(2,3),(1,3),(4,3)\}\). Determine the components.
The searches give the following queue traces and reachable sets:
| Start | Queue changes | Reachable set |
|---|---|---|
| \(1\) | \([1]\to[2,3]\to[3]\to[]\) | \(\{1,2,3\}\) |
| \(2\) | \([2]\to[3]\to[]\) | \(\{2,3\}\) |
| \(3\) | \([3]\to[]\) | \(\{3\}\) |
| \(4\) | \([4]\to[3]\to[]\) | \(\{4,3\}\) |
Vertex \(1\) reaches \(2\) and \(3\), but neither \(2\) nor \(3\) reaches \(1\). Vertex \(4\) reaches \(3\), but \(3\) cannot reach \(4\). No two distinct vertices are mutually reachable, so the four components are \(\{1\}\), \(\{2\}\), \(\{3\}\), and \(\{4\}\).
Check: A singleton component is allowed even when its vertex has outgoing or incoming arcs. The length-zero path makes each vertex reachable from itself; it does not create a path back along an arc whose direction points the other way.
A Useful Test for Strong Connectivity
Proof. If \(D\) is strongly connected, any chosen vertex \(r\) reaches every vertex and is reachable from every vertex by the definition. Conversely, suppose such an \(r\) exists. For any vertices \(u,v\), there is a path from \(u\) to \(r\) and a path from \(r\) to \(v\). Their concatenation is a directed walk from \(u\) to \(v\), and deleting repeated sections gives a directed path. This holds for every ordered pair \(u,v\), so \(D\) is strongly connected. \(\square\)
Worked Example: A Strongly Connected Directed Cycle
Let \(D=(V,A)\), where \(V=\{1,2,3,4\}\) and \(A=\{(1,2),(2,3),(3,4),(4,1)\}\). Starting at \(1\), the queue trace is \([1]\to[2]\to[3]\to[4]\to[]\), so \(1\) reaches all four vertices. The directed cycle also gives return paths: \(2\to3\to4\to1\), \(3\to4\to1\), and \(4\to1\). Thus every vertex reaches \(1\). By the proposition, the digraph is strongly connected, and its only component is \(\{1,2,3,4\}\).
Check: The arcs listed form the path \(1\to2\to3\to4\to1\). Starting at any vertex and following this sequence reaches each of the other three vertices before returning to the start, confirming the same conclusion directly.
Common Pitfall: Confusing Reachability with Mutual Reachability
A frequent error is to place \(u\) and \(v\) in the same component as soon as one can reach the other. Components require both directions. In the first example, \(a\) reaches \(d\): the path \(a\to b\to c\to d\) exists. But \(d\) cannot reach \(a\). The calculation \(d\in R(a)\), therefore \(a\sim d\), is incorrect: it omits the second condition \(a\in R(d)\). In fact, \(R(d)=\{d,e\}\), so \(a\notin R(d)\), and the vertices belong to different components.
This distinction matters in applications where arcs represent one-way possibilities, such as permitted transitions or directed communication. Strongly connected components identify the portions of a system in which every state can return to every other state. A one-way route into another portion does not make the two portions mutually accessible.
When checking a proposed list of components, use two tests: vertices placed together must be mutually reachable, and vertices in different proposed components must not be mutually reachable. The equivalence-relation theorem ensures that these tests describe a unique partition; the search procedure provides a direct way to calculate it.
Check Your Understanding
For each question, make the direction of every path explicit.
- In the digraph with \(V=\{a,b,c\}\) and \(A=\{(a,b),(b,a),(b,c)\}\), find all strongly connected components.
- Why does a vertex with no incident arcs form a strongly connected component under the length-zero-path convention?
- Prove that if \(u\) and \(v\) are in the same component, every vertex on a directed path from \(u\) to \(v\) is in that component.
- Give a digraph in which \(u\) reaches \(v\) but \(u\) and \(v\) lie in different components.
- Explain why a single search showing that \(r\) reaches every vertex is not, by itself, enough to prove strong connectivity.