Search States and Discovery
A graph traversal systematically explores vertices by following edges. The basic record of a traversal is not just a list of visited vertices: it also records when each vertex was discovered, whether its exploration is still in progress, and which vertex first discovered it. These records produce a search forest, a collection of rooted trees that describes how the traversal reached the vertices.
Throughout, graphs are finite and simple. A directed graph has arcs, and an arc from \(u\) to \(v\) is written \(uv\); it can be followed from \(u\) to \(v\), not necessarily in the reverse direction. When a vertex is explored, its outgoing neighbors are considered in a fixed order. That order, together with the chosen roots, makes a traversal trace reproducible.
Each vertex moves through the states unvisited, active, and finished in that order, with no return to an earlier state. In breadth-first search (BFS), active vertices are held in a queue: the vertex at the front is processed, then finished. In depth-first search (DFS), an active vertex remains on the recursive call stack until its outgoing neighbors have all been examined; the most recently discovered active vertex is processed first.
To make a full traversal, choose an order of vertices to use as candidate roots. When a candidate is unvisited, start a new search tree there; when it is already discovered, skip it. This procedure handles disconnected graphs and directed graphs in which some vertices cannot be reached from others. A later root may have an arc to a vertex already explored, but that arc does not become a discovery edge.
Why the Parent Pointers Form a Forest
Proof. A vertex receives a parent only when it is first discovered, and the algorithm assigns that parent once. Thus each nonroot vertex has exactly one parent, while each root has none. Each parent is already discovered when it discovers its child. Therefore, in discovery order, a parent always occurs earlier than its child. A cycle of parent pointers would require discovery order to keep moving strictly earlier and eventually return to its starting vertex, which is impossible. Since the graph is finite, following parent pointers backwards must terminate; it can terminate only at a vertex with no parent, which is a root. Hence the discovery edges form rooted trees, one for each root, and together form a forest. \(\square\)
This result depends on assigning a parent only at first discovery. An edge to an already discovered vertex may be examined, but it does not change that vertex's parent. This rule applies whether the already discovered vertex is active or finished.
Worked Example: A BFS Forest in a Directed Graph
Worked Example: A BFS Forest in a Directed Graph
Let \(G=(V,E)\) be the directed graph with \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,ac,bd,be,ce,df,ef,gc\}\). Use outgoing-neighbor order as written here: \(a:(b,c)\), \(b:(d,e)\), \(c:(e)\), \(d:(f)\), \(e:(f)\), \(f:()\), \(g:(c)\). Run a full BFS, testing candidate roots in the order \(a,b,c,d,e,f,g\).
Start at \(a\), mark it active, and put it in the queue. Each row shows the queue after processing the vertex at its front. “Active” includes vertices waiting in the queue; the vertex being processed becomes finished after its outgoing neighbors have been examined.
| Vertex processed | New discoveries and parents | Queue afterward | State change |
|---|---|---|---|
| \(a\) | \(b\) gets parent \(a\); \(c\) gets parent \(a\) | \([b,c]\) | \(a\) finished; \(b,c\) active |
| \(b\) | \(d\) gets parent \(b\); \(e\) gets parent \(b\) | \([c,d,e]\) | \(b\) finished; \(d,e\) active |
| \(c\) | \(e\) is already active | \([d,e]\) | \(c\) finished |
| \(d\) | \(f\) gets parent \(d\) | \([e,f]\) | \(d\) finished; \(f\) active |
| \(e\) | \(f\) is already active | \([f]\) | \(e\) finished |
| \(f\) | No outgoing neighbors | \([]\) | \(f\) finished |
At this point \(a,b,c,d,e,f\) are finished. The next candidate \(b\) is already visited, as are \(c,d,e,f\). Candidate \(g\) is unvisited, so it becomes a new root and is processed with queue \([g]\). Its outgoing neighbor \(c\) is already finished, so no new vertex is discovered. The queue becomes empty and \(g\) becomes finished.
The parent pointers are \(p(b)=a\), \(p(c)=a\), \(p(d)=b\), \(p(e)=b\), and \(p(f)=d\); \(a\) and \(g\) have no parent. Thus the forest has tree edges \(ab,ac,bd,be,df\), with roots \(a\) and \(g\). The original arc \(gc\) is not a forest edge: \(c\) was discovered earlier from \(a\).
Check: the five nonroot vertices \(b,c,d,e,f\) each have one parent, so there are five discovery edges. The two roots \(a,g\) and those five other vertices account for all seven vertices. Every listed parent edge is an arc of \(G\), and the parent chains terminate at \(a\) or \(g\), as the forest definition requires.
Depth-First Search and Active Vertices
DFS uses the same states and parent rule, but explores one branch as far as possible before returning to another active vertex. In the recursive version, calling DFS on a newly discovered vertex places it on the call stack. When that call has examined every outgoing neighbor, the vertex becomes finished and the call returns to its parent. The call stack therefore displays the active path through the search forest.
Worked Example: A DFS Trace on the Same Graph
Use the graph and neighbor order from the BFS example, and again test candidate roots in the order \(a,b,c,d,e,f,g\). Each stack is written with its top at the right. A neighbor that is active or finished is not rediscovered.
| Action | Stack afterward | State and parent change |
|---|---|---|
| Discover \(a\) | \([a]\) | \(a\) active; root |
| From \(a\), discover \(b\) | \([a,b]\) | \(b\) active; parent \(a\) |
| From \(b\), discover \(d\) | \([a,b,d]\) | \(d\) active; parent \(b\) |
| From \(d\), discover \(f\) | \([a,b,d,f]\) | \(f\) active; parent \(d\) |
| Finish \(f\); return to \(d\) | \([a,b,d]\) | \(f\) finished |
| Finish \(d\); return to \(b\) | \([a,b]\) | \(d\) finished |
| From \(b\), discover \(e\) | \([a,b,e]\) | \(e\) active; parent \(b\) |
| Examine \(ef\), then finish \(e\) | \([a,b]\) | \(f\) is finished; \(e\) finished |
| Finish \(b\); return to \(a\) | \([a]\) | \(b\) finished |
| From \(a\), discover \(c\) | \([a,c]\) | \(c\) active; parent \(a\) |
| Examine \(ce\), then finish \(c\) | \([a]\) | \(e\) is finished; \(c\) finished |
| Finish \(a\) | \([]\) | \(a\) finished |
| Start new root \(g\); examine \(gc\) | \([g]\), then \([]\) | \(g\) finishes; \(c\) is finished |
The DFS forest has roots \(a,g\) and discovery edges \(ab,bd,df,be,ac\). For instance, the arc \(ce\) is examined only after \(e\) has finished, so it does not give \(e\) a new parent. The forest has the same roots as the BFS forest here, but its edges differ: DFS discovers \(d\) before \(c\), while BFS discovers both \(b\) and \(c\) directly from \(a\).
Check: the forest has five edges, one for each nonroot vertex among \(a,b,c,d,e,f,g\). Each is an arc directed from its parent to its child: \(ab,bd,df,be,ac\). The remaining graph arcs \(ce,ef,gc\) do not discover a new vertex in this trace.
What a Completed Traversal Finds
Proof. First consider a search started from roots \(R\), with no additional roots. Every discovered vertex is reachable from some root: a root is reachable from itself by a walk of length zero, and whenever an explored vertex \(u\) discovers \(v\), the arc \(uv\) extends a walk from a root to \(u\) into a walk from that root to \(v\).
For the reverse inclusion, take any vertex \(v\) reachable from a root \(r\in R\). There is a directed walk \(r=v_0,v_1,\ldots,v_k=v\). The root is discovered at the start. Whenever \(v_i\) on this walk is discovered, its outgoing neighbors are eventually examined: in BFS it is eventually removed from the finite queue, and in DFS its finite list of outgoing neighbors is eventually processed before its call finishes. When the arc \(v_iv_{i+1}\) is examined, either \(v_{i+1}\) has already been discovered or it is discovered then. Repeating this reasoning along the finite walk shows that \(v\) is discovered. Thus the search discovers exactly the vertices reachable from the roots.
In a full traversal, every candidate vertex is either already discovered or is started as a new root. Therefore all vertices are discovered. By the parent-pointer theorem, each is connected to its root by discovery edges. \(\square\)
This statement concerns reachability and the structure of the search forest. It does not say that the forest contains every directed path, nor that DFS and BFS produce the same forest. Their exploration rules differ, and changing the root order or the order of outgoing neighbors can change the parent pointers.
Worked Example: Root Order and an Arc into an Earlier Tree
Let \(H=(V,E)\) have \(V=\{u,v,w,x,y\}\) and \(E=\{uv,vw,xu,xy\}\). Run a full BFS with candidate roots in the order \(u,v,w,x,y\), and examine each vertex's outgoing neighbors in the order shown by the edge list.
Start at \(u\): the queue is \([u]\). Processing \(u\) discovers \(v\) with parent \(u\), leaving queue \([v]\). Processing \(v\) discovers \(w\) with parent \(v\), leaving queue \([w]\). Processing \(w\) discovers no one, so the queue becomes empty. Candidates \(v\) and \(w\) are already discovered. Candidate \(x\) is unvisited, so start a new tree at \(x\). Processing \(x\) examines \(xu\), whose endpoint \(u\) is already finished, and then discovers \(y\) with parent \(x\). Processing \(y\) finds no outgoing neighbors.
The forest has roots \(u,x\), parent pointers \(p(v)=u\), \(p(w)=v\), and \(p(y)=x\), and discovery edges \(uv,vw,xy\). The arc \(xu\) points from the second root into the first tree; it does not merge the trees, because \(u\) already has no parent and was discovered earlier.
Check: the three nonroots \(v,w,y\) give exactly three forest edges, and the two roots \(u,x\) give five vertices altogether. The vertices reachable from \(u\) are \(u,v,w\); those reachable from \(x\) are \(x,u,v,w,y\). Their union is all of \(V\), agreeing with the full traversal.
A Common Mistake: Marking at Removal
Mark a vertex discovered and assign its parent when it is first placed in the queue or call stack—not later when it is processed. Otherwise, two different vertices may both treat the same queued vertex as unvisited.
For a concrete wrong calculation, take the directed graph \(V=\{r,a,b\}\), \(E=\{ra,rb,ab\}\), with \(r\)'s neighbors ordered \(a,b\). Suppose BFS delays marking until removal. It removes \(r\), sees both \(a\) and \(b\) as unvisited, and enqueues both, giving queue \([a,b]\). It then removes \(a\), sees \(b\) as still unvisited under this incorrect rule, and enqueues \(b\) again with the apparent parent \(a\). Now the queue is \([b,b]\), and \(b\) has been assigned competing discovery records.
The correction is to mark vertices active as soon as they are enqueued. After processing \(r\), both \(a\) and \(b\) are active and the queue is \([a,b]\), with parent pointers \(p(a)=r\) and \(p(b)=r\). When \(a\) examines \(ab\), it sees that \(b\) is already active and does not enqueue it again. The final discovery edges are \(ra,rb\), which form the correct rooted tree.
Check Your Understanding
Use the state definitions and parent-pointer rule to answer the following.
- In a traversal, what distinguishes an active vertex from a finished vertex?
- Let \(V=\{s,t,u\}\) and \(E=\{st,su,tu\}\), with outgoing neighbors ordered \(t,u\). Trace BFS from \(s\), recording the queue and both parent pointers.
- Why can an arc from a later root to a vertex in an earlier tree fail to be a discovery edge?
- Prove that a vertex's parent cannot be changed after it has been discovered if the first-discovery rule is followed.
- For a search started from a single root in a directed graph, does it discover every vertex in the underlying undirected component? Explain why or why not.