Directed Walks and Reachability

Following Arcs in a Directed Graph

In an undirected graph, an edge can be followed in either direction. In a digraph, each arc has a specified direction, so a sequence of adjacent vertices is useful only when every step follows its arc in the forward direction. This distinction matters when asking which vertices can be reached from a starting point: two vertices may be connected by an arc in one direction without being reachable from one another.

Throughout, a digraph is finite, has no loops or parallel arcs, and may contain both arcs \(uv\) and \(vu\). Write \(uv\) for the arc directed from \(u\) to \(v\). A sequence of vertices follows a directed route only when each consecutive pair is an arc in the listed direction.

Thus, every directed path is a directed trail and every directed trail is a directed walk, but the reverse implications need not hold. The length is the number of arcs traversed, not the number of listed vertices. A walk may return to its starting vertex; that does not make it a path unless it has length zero.

Reachability

Including the length-zero path makes reachability reflexive: \(u\in R(u)\) for every vertex \(u\). Reachability follows arc direction, and it need not be symmetric. For example, the arc \(uv\) gives a path from \(u\) to \(v\), but by itself gives no path from \(v\) to \(u\).

Proof. Among all directed walks from \(u\) to \(v\), choose one of minimum length; such a minimum exists because the lengths are nonnegative integers and the set of possible lengths is nonempty. Write it as \(v_0,v_1,\ldots,v_\ell\). If a vertex repeats, then \(v_i=v_j\) for some \(0\le i<j\le\ell\). Delete the portion \(v_i,v_{i+1},\ldots,v_j\), retaining \(v_i\) and continuing with \(v_{j+1}\) if \(j<\ell\). This is still a directed walk: when \(j<\ell\), the required next arc is \(v_jv_{j+1}\), and \(v_i=v_j\), so that same arc goes from \(v_i\) to \(v_{j+1}\). If \(j=\ell\), then \(v_i=v_\ell=v\), so the shortened sequence still ends at \(v\). In either case the endpoints are unchanged and the length decreases by \(j-i>0\), contradicting minimality. Thus the minimum-length walk has no repeated vertices and is a path. When \(u=v\), the length-zero path already gives the conclusion. \(\square\)

This lemma means that reachability can equivalently be tested by asking whether any directed walk exists. It also shows why repeated vertices in a route do not create new reachable endpoints: a section that leaves a vertex and later returns to it can be removed.

Proof. Take a directed path from \(u\) to \(v\) and a directed path from \(v\) to \(w\). Follow the first path and then the second. The result is a directed walk from \(u\) to \(w\), because both sequences meet at \(v\) and every step follows an arc. By the Lemma, a directed walk from \(u\) to \(w\) contains a directed path with the same endpoints. Therefore \(w\) is reachable from \(u\). The argument also covers length-zero paths when \(u=v\) or \(v=w\). \(\square\)

Finding a Reachable Set by Breadth-First Search

For a finite digraph, breadth-first search (BFS) systematically explores outward from a chosen start vertex \(s\). It stores discovered vertices in a queue, a list in which the earliest inserted vertex is processed first. Give \(s\) distance label \(0\). Whenever a vertex with label \(k\) is processed, inspect each arc leaving it; any undiscovered endpoint receives label \(k+1\) and is added to the back of the queue. Record the arc by which each vertex was first discovered as its predecessor arc. Stop when the queue is empty.

Proof. First, every discovered vertex is reachable: \(s\) is reachable by the length-zero path, and each later discovery follows an arc from a vertex already known to be reachable. Appending that arc to a path to the earlier vertex gives a directed walk; the Lemma supplies a path to the newly discovered vertex.

Now consider any vertex \(v\) reachable from \(s\), and take a shortest directed path \(s=v_0,v_1,\ldots,v_k=v\). We show in order along this path that BFS discovers each \(v_i\). It starts with \(v_0=s\). If \(v_i\) is discovered, it is eventually processed because the graph is finite and the queue continues until empty. When it is processed, the arc \(v_iv_{i+1}\) is inspected. The endpoint \(v_{i+1}\) is then either already discovered or is added to the queue. Thus \(v\) is discovered. This proves that the discovered set is exactly \(R(s)\).

For the distance claim, a vertex assigned label \(k\) has a predecessor chain of \(k\) arcs back to \(s\), so there is a path of length \(k\). To see that no shorter path exists, suppose a path of length \(j\) reaches a vertex \(v\). Its vertices occur in order along the path. Starting with \(s\) at label \(0\), each arc can lead to a discovery at most one level later; processing vertices in queue order ensures every vertex at a smaller label is processed before one at a larger label. Following the path therefore shows that \(v\) is discovered with label at most \(j\). Taking \(j\) to be the shortest possible path length shows the BFS label is no greater than that distance. Combined with the predecessor path of length equal to the label, the label is exactly the shortest distance. \(\square\)

Common Pitfalls and Uses

Wrong calculation: In the preceding digraph, one might treat \(ab\) as if it also allowed travel from \(b\) to \(a\), then claim \(a\in R(b)\). That reverses the arc: \(ab\) means \(a\) to \(b\), not \(b\) to \(a\). Checking the actual outgoing arcs from \(b\), only \(bd\) leaves \(b\); in fact \(R(b)=\{b,d,e,f,g\}\), using \(b,d,e\) and \(b,d,f,g\) as paths where needed. More precisely, \(b\) reaches \(d\), then \(e\) and \(f\), and then \(g\); it does not reach \(a,c,\) or \(h\). The correction is to follow only arcs whose tails are at vertices already reached.

Reachability is a basic way to describe what can be accessed from a starting state, location or task when transitions have direction. In computation, BFS finds the reachable set and shortest path lengths in a finite unweighted digraph. It can also provide an actual route: tracing predecessor arcs backward from a discovered vertex, then reversing that list, gives a directed path from the start.

Keep the three questions separate: a walk allows repeated vertices and arcs; a trail forbids repeated arcs; a path forbids repeated vertices. Reachability asks whether at least one path exists, not how many walks there are. In particular, cycles can create arbitrarily long walks without changing which vertices are reachable.