Graph Traversals: BFS & DFS

Graph traversal is controlled discovery. Both breadth-first search (BFS) and depth-first search (DFS) start from known vertices, expose outgoing edges, and prevent repeated discovery. One data-structure choice changes the shape of the entire computation: a FIFO queue makes BFS expand in distance layers, while a stack of suspended adjacency scans makes DFS produce nested subtrees and finish times.

The algorithms are valuable less as ways to “visit everything” than as proof frameworks. Their predecessor forests certify reachability; BFS layers certify minimum edge counts; DFS intervals expose cycles, ordering, and component structure.

The shared traversal contract #

A traversal must declare:

• a directed or undirected graph and the neighbor relation it follows;
• one source, several sources, or a whole-graph root order;
• when a vertex becomes discovered and when it becomes finished;
• which outputs are recorded: predecessors, distances, timestamps, edges, or callback events;
• whether adjacency may change during the run.

Use three semantic states:

Undiscovered (white)

No traversal path to the vertex has yet been recorded.

Discovered (gray or active/frontier)

A predecessor path is known, but some required processing remains.

Finished (black)

The algorithm has examined every relevant outgoing edge of the vertex.

The colors are conventional encodings; the state meanings are the invariant. A Boolean seen flag can be enough for reachability, but it cannot distinguish active from finished vertices when DFS cycle logic needs that distinction.

Whenever a previously undiscovered vertex $v$ is reached through edge $(u,v)$, set $parent[v]=u$. Every non-root parent edge is a real graph edge, so following parents produces a concrete path back to a root. These edges form a tree for one root, or a predecessor forest when traversal restarts in multiple components.

Why discovery is sound and complete #

Traversal discovery has two directions to prove:

1. Soundness: every discovered vertex is reachable. The source is reachable by the empty path. Every later discovery extends an already certified path by one real edge.
2. Completeness: every reachable vertex is eventually discovered. Take a source-to-target path and assume the first undiscovered vertex on it remains after termination. Its predecessor on the path was discovered, so its outgoing edge had to be examined, a contradiction.

The second argument relies on actually scanning every relevant edge of every discovered vertex. Early stopping or filtered neighbors changes the contract and therefore the reachable set being certified.

BFS: a FIFO frontier creates layers #

Standard BFS marks a vertex when it is enqueued, not when it is later removed:

for each vertex v:
    state[v] = undiscovered
    distance[v] = infinity
    parent[v] = none

state[source] = discovered
distance[source] = 0
enqueue(source)

while queue is not empty:
    u = dequeue()
    for each v in out_neighbors(u):
        if state[v] == undiscovered:
            state[v] = discovered
            distance[v] = distance[u] + 1
            parent[v] = u
            enqueue(v)
    state[u] = finished

The queue contains discovered vertices whose adjacency scans are pending. Immediate marking reserves the vertex: the first edge to find it establishes its parent and distance, and no later edge enqueues it again.

The queue invariant #

At the start of each loop iteration:

1. every queued vertex has a path of exactly its recorded distance;
2. queued distances are nondecreasing from front to back;
3. the queue contains at most two consecutive distance values, say $k$ and $k+1$;
4. every vertex with distance below the front’s distance has been finished.

Why does FIFO preserve this? When a distance-$k$ vertex leaves the front, every newly discovered neighbor receives $k+1$ and is appended behind all vertices already queued. No operation can insert a smaller layer behind a larger one.

Why BFS finds minimum-edge paths #

For an unweighted graph, define $\delta(s,v)$ as the minimum number of edges on a path from $s$ to $v$, or infinity if none exists. BFS records a predecessor path of length $distance[v]$, so

$$\delta(s,v)\le distance[v].$$

The opposite inequality follows by induction on true path length. Suppose every vertex at distance at most $k$ is discovered with its correct distance. Let $v$ be at distance $k+1$, and let $u$ precede it on a shortest path. Then $\delta(s,u)=k$. BFS discovers and processes $u$ before any layer beyond $k+1$; examining $(u,v)$ either discovers $v$ with $k+1$ or finds that $v$ already received an equal-or-smaller distance. Therefore

$$distance[v]\le k+1=\delta(s,v).$$

Together the inequalities give equality.

The proof says exactly what BFS minimizes: edge count in the traversed graph. It does not minimize arbitrary weights, latency, risk, or any other edge attribute. Those require Shortest Paths.

Multiple shortest paths may exist. The distance is invariant, while the chosen parent depends on which equal-layer predecessor is scanned first.

A complete BFS trace #

Use this directed graph. The subgraphs show BFS distance layers from s; g is unreachable.

flowchart LR
  subgraph L0["distance 0"]
    s((s))
  end
  subgraph L1["distance 1"]
    a((a))
    b((b))
  end
  subgraph L2["distance 2"]
    c((c))
    d((d))
    e((e))
  end
  subgraph L3["distance 3"]
    f((f))
  end
  subgraph U["unreachable"]
    g((g))
  end
  s --> a
  s --> b
  a --> c
  a --> d
  b --> d
  b --> e
  c --> f
  d --> c
  d --> f
  e --> d
  f --> b

Assume alphabetic adjacency order. The queue trace is:

One BFS tree has parents

$$a\leftarrow s,\quad b\leftarrow s,\quad c\leftarrow a,\quad d\leftarrow a,\quad e\leftarrow b,\quad f\leftarrow c.$$

Reversing some adjacency orders can make b the parent of d and d the parent of f, but the four distance layers remain the same.

Useful BFS variants #

• Multi-source BFS: enqueue every source initially at distance 0. The result gives distance to the nearest source in edge count.
• Early target stop: stop when the target is dequeued—or even when discovered if only its BFS distance/path is needed, because discovery fixes that distance.
• Depth limit: do not expand vertices at the limit; the result certifies reachability only within that radius.
• Reverse traversal: in a directed graph, follow incoming rather than outgoing edges, requiring an incoming index or a reversed graph view.

Changing the FIFO buffer changes the theorem. A stack gives depth-first behavior; a priority queue ordered by tentative cost leads toward Dijkstra’s algorithm. The buffer is not an incidental implementation detail.

DFS: suspended work creates depth #

Recursive DFS expresses its state directly in the call stack:

visit(u):
    state[u] = active
    discover_time[u] = ++time
    for each v in out_neighbors(u):
        if state[v] == undiscovered:
            parent[v] = u
            visit(v)
    state[u] = finished
    finish_time[u] = ++time

DFS follows an undiscovered neighbor immediately. It returns to $u$ only after that neighbor’s entire recursive subtree is finished, then resumes $u$’s adjacency scan where it stopped.

The decisive invariant is:

This is why “replace recursion with a stack” needs precision. An equivalent explicit implementation stores frames such as (u, next_neighbor_index). A simpler algorithm that pushes every neighbor as a bare vertex may still find all reachable vertices, but it can produce different parents, discovery/finish events, and edge classifications.

Exact iterative DFS #

1. Mark the root active and push a frame whose neighbor iterator is at its beginning.
2. Inspect the top frame:
   • if another outgoing edge exists, advance the iterator;
   • if its target is undiscovered, record the parent, mark it active, and push a new frame;
   • otherwise classify/process the edge and keep the frame;
3. if no neighbor remains, mark the top vertex finished, record its finish time, and pop.

The explicit stack uses the same worst-case $O(V)$ depth as recursion but avoids dependence on the language’s call-stack limit.

DFS intervals and the parenthesis theorem #

Record an increasing timestamp on discovery $d[v]$ and finish $f[v]$. A vertex is active exactly during the open interval between those events.

For any two vertices $u$ and $v$ in a DFS forest, their intervals are either disjoint or one contains the other:

$$[d[u],f[u]]\cap[d[v],f[v]]=\varnothing,$$

or

$$d[u]<d[v]<f[v]<f[u],$$

or the symmetric containment. Partial overlap is impossible because a call cannot finish while a descendant frame remains above it.

Containment has structural meaning: $u$ is an ancestor of $v$ in the DFS tree exactly when $u$’s interval strictly contains $v$’s.

Run alphabetic DFS on the earlier graph, then restart at isolated g:

The active path reaches s→a→c→f→b→d. Edge d→c then points to an active ancestor, certifying the directed cycle

$$c\to f\to b\to d\to c.$$

Directed DFS edge classes #

When an edge $(u,v)$ is examined in a directed graph:

In the trace, a→d is forward because d became a descendant through a→c→f→b→d; e→d is cross because d finished before e was discovered.

For an undirected graph, each edge is commonly exposed from both endpoints. The incidence back to a vertex’s parent is not a new cycle edge. Cycle detection must ignore that parent twin (or distinguish edge IDs in a multigraph). Do not apply the directed gray-target rule without this adjustment.

From one source to a whole-graph forest #

A source traversal visits only its reachable set. To cover every vertex:

initialize all vertices as undiscovered
for each vertex r in a declared root order:
    if r is undiscovered:
        start a traversal at r

Each restart creates a tree root. In an undirected graph, these trees coincide with connected components. In a directed graph, they are traversal trees determined by root and adjacency order—not strongly connected components.

The order matters for the concrete forest but not for the fact that every vertex is eventually covered.

DFS as an algorithmic scaffold #

DFS exposes event points—discover vertex, examine edge, finish vertex—on which stronger algorithms build.

Directed cycle detection #

A directed graph has a cycle if and only if a complete DFS encounters a back edge to an active vertex. One direction was shown above. For the other, take the first vertex of any reachable cycle discovered; before it can finish, DFS follows the cycle through still-undiscovered vertices until an edge returns to an active vertex.

Topological ordering #

A topological order lists every directed edge $u\to v$ with $u$ before $v$. It exists exactly for a directed acyclic graph (DAG). In a DFS with no back edge, decreasing finish time is a topological order: for every edge $u\to v$, either DFS explores $v$ beneath $u$, so $f[v]<f[u]$, or $v$ is already finished, again giving $f[v]<f[u]$.

If a back edge appears, reject the order and return a cycle witness. Merely reversing finish order without cycle detection does not turn a cyclic graph into a DAG.

Components and lowlink algorithms #

Repeated DFS directly finds undirected connected components. Strongly connected and biconnected components need additional stack/lowlink invariants. Tarjan’s 1972 work demonstrates how DFS structure supports linear-time algorithms for those problems, but their full mechanisms are distinct from basic traversal and should not be guessed from the DFS timestamps alone.

Complexity is representation-sensitive #

Assume an explicit adjacency representation where iterating all outgoing records of $u$ costs $\Theta(\deg^+(u))$.

• each vertex changes from undiscovered once and enters the queue/stack at most once;
• each outgoing incidence is examined once in a directed graph;
• in a usual undirected layout, each edge contributes two incidences.

Therefore BFS and DFS take

$$\Theta(V+E)$$

time and $O(V)$ auxiliary state for colors, parents, distances/timestamps, and frontier/stack.

Over an adjacency matrix, finding neighbors scans a $V$-cell row. Repeating this for $V$ reached vertices costs $\Theta(V^2)$ even if the graph has only $\Theta(V)$ edges. The abstract algorithm is unchanged; the out_neighbors primitive is not. See Graph Representations for the full cost model.

DFS’s recursive call depth can be $V$ on a path. BFS’s queue can contain $O(V)$ vertices on a wide layer. Both use linear worst-case auxiliary space, but their peak shapes differ.

Determinism and mutation #

Traversal order is not normally a graph invariant. It depends on:

• root order;
• order of outgoing adjacency;
• when state transitions occur;
• whether parallel edges are collapsed;
• callbacks or filters that alter which neighbors are considered.

If reproducible output matters, sort neighbors or use a representation with a documented stable order and include that cost in the contract.

Mutating adjacency during traversal invalidates ordinary proofs unless semantics are defined. Adding an edge after its source is finished may hide a newly reachable vertex; deleting one may invalidate an iterator or recorded parent. Safe choices are: forbid mutation, traverse a snapshot, or use a separately proven dynamic algorithm.

Failure diagnostics #

1. Was a vertex marked at discovery or only after removal?
2. Does the buffer obey FIFO for BFS, or preserve suspended frames for exact DFS?
3. Is the traversal following outgoing, incoming, or undirected adjacency?
4. Was the run single-source or restarted over all undiscovered vertices?
5. Are distances measured in edge count, and are all edges equal-cost for that purpose?
6. Does edge classification match directed/undirected and simple/multigraph semantics?
7. Is a claimed order invariant under neighbor reordering, or merely one execution trace?
8. Does the complexity include the representation’s neighbor-iteration cost?
9. Could recursion depth overflow, or could graph mutation invalidate state?

Exercises #

1. Run BFS from s on the example with s’s neighbors ordered b,a and every other list alphabetic. Give distances and parents.
2. Prove that every parent edge in a BFS tree goes from layer $k$ to layer $k+1$.
3. Give a graph where the BFS queue contains $\Theta(V)$ vertices at once and a graph where recursive DFS reaches depth $\Theta(V)$.
4. In the recorded DFS trace, classify d→f, a→d, e→d, and s→b.
5. Explain why an undirected edge from a child back to its parent must not automatically be reported as a cycle.
6. Produce a topological order for edges p→q, p→r, q→s, r→s, then add one edge that makes an order impossible and give the cycle.
7. An adjacency matrix represents a graph with $V$ vertices, but a traversal reaches only $R$ of them. Give a precise row-scan bound in terms of $R$ and $V$.