One Root, One Reachability Search
Breadth-first search (BFS) explores from a chosen starting vertex in layers of increasing distance. In an undirected graph, one search reaches every vertex in the root's connected component. In a directed graph, however, only arcs pointing in the direction of travel can be followed. A vertex can be connected to the root if directions are ignored and still be unreachable from it.
For a directed graph, write \(u\to v\) for an arc from \(u\) to \(v\). A directed path from \(r\) to \(v\) is a sequence beginning at \(r\), ending at \(v\), and following each arc in its direction. A vertex is reachable from \(r\) if such a path exists; \(r\) is reachable from itself by a path of length zero. The underlying undirected graph is obtained by ignoring the directions of all arcs. Vertices in the same connected component of this graph need not be mutually reachable, or even reachable from one another.
The directed BFS distance \(d(r,v)\) is the minimum length of a directed path from \(r\) to \(v\), when one exists. The root has distance zero. Each newly discovered vertex \(v\), first reached from a dequeued vertex \(u\), receives distance \(d(r,u)+1\) and parent \(u\). The queue ensures that vertices are processed in nondecreasing distance order. A directed search does not follow an incoming arc backwards.
What a Directed Search Finds
Proof. First, every discovered vertex has a directed path from \(r\). The root has the length-zero path. Whenever an undiscovered vertex \(v\) is discovered while processing \(u\), the arc \(u\to v\) exists. If \(u\) has a directed path from \(r\), appending \(u\to v\) gives a directed path to \(v\). Induction on the order of discovery proves this for every discovered vertex.
Conversely, take any vertex \(v\) reachable from \(r\), and choose a directed path \(r=v_0\to v_1\to\cdots\to v_k=v\). We show successively that each \(v_i\) is discovered. The root \(v_0=r\) is discovered initially. If \(v_i\) is discovered, it is eventually dequeued: the queue is finite, and each vertex is enqueued at most once. When \(v_i\) is processed, its outgoing arc \(v_i\to v_{i+1}\) is examined. If \(v_{i+1}\) was not already discovered, BFS discovers it then; otherwise it is already discovered. Thus every vertex on the path, including \(v\), is discovered. Together, the two directions show that the discovered set is exactly the reachable set. The parent arcs point along the directed paths constructed in the first part, so they form a search tree rooted at \(r\). \(\square\)
Worked Example: Reachable Does Not Mean Weakly Connected
Let \(G\) be the directed graph with \(V=\{r,a,b,c,d,e\}\) and arcs \(r\to a\), \(r\to b\), \(a\to c\), \(b\to c\), \(c\to a\), \(d\to c\), and \(e\to d\). Start BFS at \(r\), examining each vertex's outgoing neighbors in alphabetical order.
| Dequeued vertex | New discoveries | Queue after processing |
|---|---|---|
| Initial state | \(r\) is the root | \([r]\) |
| \(r\) | \(a,b\) | \([a,b]\) |
| \(a\) | \(c\) | \([b,c]\) |
| \(b\) | None; \(c\) is already discovered | \([c]\) |
| \(c\) | None; \(a\) is already discovered | \([]\) |
The search discovers \(r,a,b,c\). Their distances are \(d(r,r)=0\), \(d(r,a)=1\), \(d(r,b)=1\), and \(d(r,c)=2\). Their parent arcs are \(r\to a\), \(r\to b\), and \(a\to c\). The arc \(b\to c\) does not change \(c\)'s parent, because \(c\) was already discovered.
The vertices \(d\) and \(e\) are not reached: the arcs \(d\to c\) and \(e\to d\) point toward the reached part, not away from it. If directions are ignored, all six vertices lie in one connected component, since the underlying edges link \(e\) to \(d\), \(d\) to \(c\), and \(c\) to the rest. Thus this root's BFS tree is not a tree for the whole underlying component.
Check: The parent arcs form the directed paths \(r\), \(r\to a\), \(r\to b\), and \(r\to a\to c\). Each path follows the listed arcs, and no directed path from \(r\) can continue to \(d\) or \(e\): the only arc incident from the reached part toward those vertices would need to be an arc out of \(c\) toward \(d\), and no such arc exists.
Restarting BFS in a Disconnected Undirected Graph
A single BFS in an undirected graph reaches only the connected component containing its root. To visit every vertex, scan the vertices in a fixed order. Whenever the scan finds a vertex not yet discovered, start a new BFS from it. The result is a search forest: a collection of BFS trees, one for each connected component. An isolated vertex is a component by itself and contributes a one-vertex tree.
Proof. Every vertex is eventually discovered: it is either discovered during an earlier search or encountered by the scan and used as a new root. Each tree lies within one connected component, since every parent edge is an edge of \(G\). Now fix a connected component \(C\), and consider the first vertex of \(C\) encountered by the scan that has not already been discovered. It becomes a root. Every vertex of \(C\) is connected to that root by an undirected path. Along the path, each vertex is discovered once its preceding vertex is processed, because BFS examines all incident edges. Hence that search discovers all of \(C\). No later vertex in \(C\) can start another tree, since all of \(C\) is already discovered. Therefore each component contributes exactly one tree, including a singleton component with no edges. \(\square\)
Worked Example: A Search Forest for a Disconnected Graph
Let the undirected graph have \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,13,24,35,45,67\}\). Scan vertices in the order \(1,2,\ldots,8\); within each search, examine neighbors in increasing numerical order.
At vertex \(1\), start the first BFS. The trace is:
| Dequeued vertex | New discoveries | Queue after processing |
|---|---|---|
| Initial state | \(1\) is the root | \([1]\) |
| \(1\) | \(2,3\) | \([2,3]\) |
| \(2\) | \(4\) | \([3,4]\) |
| \(3\) | \(5\) | \([4,5]\) |
| \(4\) | None; \(5\) is already discovered | \([5]\) |
| \(5\) | None; \(4\) is already discovered | \([]\) |
The first tree has root \(1\), parent edges \(12,13,24,35\), and distances \(0,1,1,2,2\) for vertices \(1,2,3,4,5\), respectively. The remaining edge \(45\) joins two already discovered vertices, so it is not a tree edge. The next undiscovered vertex in scan order is \(6\). Its search discovers \(7\) by edge \(67\), giving a second tree with root \(6\), parent \(7\), and distances \(0,1\). Vertex \(8\) is still undiscovered when scanned, so it starts a third tree by itself, with distance zero.
The output forest has roots \(1,6,8\) and three trees. As a check, the graph's components are \(\{1,2,3,4,5\}\), \(\{6,7\}\), and \(\{8\}\): within the first set, each vertex connects to \(1\) by one of the listed paths; there is no edge from that set to \(6,7,8\); and \(8\) has no incident edge. These are exactly the three sets covered by the searches.
A Directed Full Traversal Is Not a Component Decomposition
The same scan-and-restart procedure can be run on a directed graph, following outgoing arcs. It will visit all vertices, but the resulting search trees do not in general correspond to strongly connected components or to the set of vertices reachable from each possible root. A vertex already discovered by an earlier search is not searched again, even if a later root could reach it. Thus the forest records the order in which the algorithm first covers vertices, not every directed reachability relation.
Worked Example: The Root Order Changes the Directed Forest
Let the directed graph have \(V=\{p,q,r,s,t\}\) and arcs \(p\to q\), \(q\to p\), \(r\to q\), \(s\to r\), and \(t\to s\). First scan the vertices in the order \(p,q,r,s,t\), following outgoing arcs. Starting at \(p\) discovers \(q\), and processing \(q\) finds \(p\) already discovered. When the scan reaches \(r\), it starts a new tree; its outgoing neighbor \(q\) has already been discovered. The same happens at \(s\) and \(t\).
| Scan event | Action | New tree or discovery |
|---|---|---|
| \(p\) | Start BFS; process \(p\) | \(p\) discovers \(q\) |
| \(q\) | Process \(q\) | \(p\) is already discovered |
| \(r\) | Start BFS; process \(r\) | \(q\) is already discovered |
| \(s\) | Start BFS; process \(s\) | \(r\) is already discovered |
| \(t\) | Start BFS; process \(t\) | \(s\) is already discovered |
The resulting forest has roots \(p,r,s,t\), and its only parent arc is \(p\to q\). Yet a separate BFS started at \(t\) reaches every vertex: its path is \(t\to s\to r\to q\to p\). The distances from \(t\) are \(d(t,t)=0\), \(d(t,s)=1\), \(d(t,r)=2\), \(d(t,q)=3\), and \(d(t,p)=4\). This does not contradict the forest trace: that trace has already marked \(s,r,q,p\) before the scan reaches \(t\), so it does not conduct a fresh search from \(t\).
Check: Each step on the path from \(t\) follows one of the listed arcs, so all five vertices are reachable from \(t\). In the full scan, however, the earlier roots prevent those vertices from being newly discovered from \(t\). The forest depends on scan order; the set reachable from a specified root does not.
Common Pitfalls and Why the Distinction Matters
Reversing an arc. In the first example, it would be wrong to report that \(d\) is at distance \(3\) from \(r\) by tracing \(r\to a\to c\) and then using the edge \(d\to c\) backwards. That is not a directed path: the listed arc goes from \(d\) to \(c\), not from \(c\) to \(d\). The correction is to examine only outgoing arcs, which leaves \(d\) and \(e\) undiscovered from \(r\).
Confusing a search tree with a whole graph component. A BFS tree contains only the edges that first discover vertices. In the undirected example, edge \(45\) belongs to the graph and to the same component, but it is not a parent edge. In a disconnected graph, one tree cannot cover every component; the complete traversal is a forest.
Using one root when all vertices must be covered. If the task is to find all vertices reachable from \(r\), stop after that BFS: restarting at other vertices would answer a different question. If the task is to visit every vertex of an undirected graph, use the scan-and-restart procedure. In directed graphs, be explicit about which task is intended, because a full traversal forest is not a list of all root reachability sets.
These distinctions are useful whenever a graph models one-way movement, dependencies, or communication links. The direction of each edge determines which transitions a search may take; in an undirected network, restarting from undiscovered vertices provides coverage of every connected component without confusing that coverage with a single-root search.
Check Your Understanding
For each question, state whether it asks about a single-root reachable set or a full traversal forest.
- In a directed graph with arcs \(u\to v\) and \(w\to v\), can a search from \(u\) reach \(w\) by following the second arc backwards? Explain.
- For the directed graph in the first worked example, list the vertices reachable from \(d\). Give a directed path from \(d\) to each one.
- Why does the undirected graph in the second worked example produce three search trees rather than one?
- In the directed graph in the third worked example, why is \(p\) not newly discovered when the scan starts at \(t\)?
- For a finite undirected graph with an isolated vertex, what does that vertex contribute to a full BFS search forest?