DFS and BFS Basics

1Introduction

This lecture defines depth-first search and breadth-first search through their management of candidate vertices and explains why a visited set is necessary, why both traversals correctly characterize reachability, their complexity, and why BFS computes unweighted shortest-path distances.

Linear search and binary search locate a target value in an array. This lecture instead considers traversals that enumerate graph vertices by following edges.

The lecture assumes the definitions of vertices, edges, adjacency, paths, and distance. Review Graph Basics first if these concepts are unfamiliar.

2A common traversal framework

Let $$G=(V,E)$$G=(V,E) be a graph with a starting vertex $$s\in V$$s\in V. A traversal stores discovered vertices whose neighbors have not yet been fully examined as candidates.

1. Initialize the visited set as $$S=\left\{s\right\}$$S=\{s\} and add $$s$$s to the candidates.
2. While candidates remain, remove one vertex $$v$$v.
3. For each neighbor $$u\in N\left(v\right)$$u\in N(v), if $$u\notin S$$u\notin S, add $$u$$u to both $$S$$S and the candidates.

A vertex must be marked visited when it is added. If marking is delayed until removal, multiple edges may add the same vertex repeatedly.

3DFS

Depth-first search (DFS) manages candidates with a stack and prioritizes the most recently added candidate. In a recursive implementation, DFS chooses one unexamined neighbor and completes that recursive call before examining the next neighbor. It therefore extends one path and then backtracks.

In a recursive implementation, the function-call stack acts as the candidate stack. Even in the recursive version, a visited set is required for termination on graphs containing cycles.

4BFS

Breadth-first search (BFS) manages candidates with a queue. When BFS first discovers a vertex $$u$$u from its parent $$v$$v, it records the traversal level

with $$\ell \left[s\right]=0$$\ell[s]=0. The next section proves that this level equals the shortest-path distance in an unweighted graph.

5Why BFS gives shortest distances

Let $$\delta (s,u)$$\delta(s,u) denote the true shortest-path distance. The parent chain by which BFS discovers $$u$$u is a path of length $$\ell \left[u\right]$$\ell[u], so $$\delta (s,u)\le \ell \left[u\right]$$\delta(s,u)\leq \ell[u].

A vertex added from a level-$$k$$k vertex has level $$k+1$$k+1 and is placed after vertices already in the queue. FIFO order therefore makes queue removals occur in nondecreasing level order. We prove the reverse inequality by induction on $$r=\delta (s,u)$$r=\delta(s,u). The case $$r=0$$r=0 is the start vertex. For $$r>0$$r>0, let $$w$$w be the predecessor of $$u$$u on a shortest path. By the induction hypothesis, $$\ell \left[w\right]=r-1$$\ell[w]=r-1. When $$w$$w is processed, either it discovers $$u$$u at level $$r$$r or $$u$$u has already been discovered at a level at most $$r$$r. Hence $$\ell \left[u\right]\le \delta (s,u)$$\ell[u]\leq\delta(s,u), and the two inequalities give $$\ell \left[u\right]=\delta (s,u)$$\ell[u]=\delta(s,u).

This claim is restricted to unweighted graphs, where every edge has equal cost. Graphs with unequal nonnegative edge weights require another method, such as Dijkstra's algorithm.

6Reachability and termination

Every visited vertex is reached by extending a known path by one edge, so it is reachable from the start. Conversely, use induction on the length $$r$$r of a path from the start. The case $$r=0$$r=0 is the start vertex. For $$r>0$$r>0, the preceding vertex is discovered by the induction hypothesis. Because the finite candidate set is processed in turn, that vertex is eventually removed and discovers the next vertex. Hence both DFS and BFS visit every reachable vertex exactly once.

In a finite graph, each vertex is added to the candidates at most once, so the traversal terminates.

7Complexity

With adjacency lists, each vertex is processed once, and each undirected edge is examined at most once from each endpoint. Therefore both DFS and BFS take

time and require $$O\left(\right|V\left|\right)$$O(|V|) additional space for the visited set and candidates.

8Choosing between them

• Either DFS or BFS can enumerate reachable vertices and connected components.
• Use BFS for unweighted shortest distances and minimum-step problems.
• DFS is suitable for recursive structure, postorder processing, and prioritizing deeper candidates.
• Do not apply ordinary BFS to shortest paths with unequal edge weights.

9Summary

• The essential difference between DFS and BFS is whether candidates are managed by a stack or a queue.
• The visited set prevents nontermination on cycles and duplicate candidates.
• Both traversals visit each reachable vertex exactly once and run in $$O\left(\right|V|+|E\left|\right)$$O(|V|+|E|) time with adjacency lists.
• BFS processes layers in distance order and therefore computes shortest distances in unweighted graphs.