11.3 BFS, DFS, and Shortest Paths

Section 11.2 found a connected component by repeatedly expanding from reached vertices. An algorithm must make one more choice: when several reached vertices still have unexplored neighbors, which one should be processed next?

Two different answers produce breadth-first search and depth-first search. Both reach exactly the vertices in the start vertex's component, but their exploration shapes are different.

Search state: discovered, processed, and frontier

Fix a start vertex $s$. During a graph search, each vertex is in one of three conceptual states:

• undiscovered: the search has not reached it;

• discovered: the search has reached it but may not have inspected all its neighbors;

• processed: all its neighbors have been inspected.

The frontier stores discovered vertices waiting to be processed. Mark a vertex discovered when it first enters the frontier, not when it later leaves. Otherwise, two vertices could add the same neighbor repeatedly.

Whenever a vertex $v$ is first discovered from $u$, record $u$ as its predecessor, written $\operatorname{pred}(v)=u$. The predecessor edges form a tree rooted at $s$, called a search tree. This does not claim the original graph is a tree; it records only the first-discovery route to each reached vertex.

To make every trace reproducible, we will inspect each adjacency list in alphabetical order. A different neighbor order may produce a different valid search tree.

Breadth-first search uses a queue

A queue is a first-in, first-out structure: the earliest inserted item leaves first. Breadth-first search (BFS) stores its frontier in a queue.

Starting at $s$:

1. mark $s$ discovered and enqueue it;

2. dequeue the front vertex $u$;

3. inspect each neighbor $v$ of $u$;

4. whenever $v$ is undiscovered, mark it discovered, set $\operatorname{pred}(v)=u$, and enqueue it;

5. mark $u$ processed and repeat until the queue is empty.

Consider the adjacency lists

BFS from $A$ evolves as follows:

The resulting layers are

Every vertex in $L_i$ is exactly $i$ edges from $A$ along a shortest path.

Why BFS finds unweighted shortest paths

In an unweighted graph, the distance $d(s,v)$ is the minimum number of edges in any path from $s$ to $v$. If no path exists, define $d(s,v)=\infty$.

BFS processes all vertices at distance $i$ before any vertex at distance $i+1$. When an edge from layer $L_i$ first discovers $v$, it creates a path of length $i+1$. A shorter path would have had to reach $v$ from an earlier layer, so $v$ would already have been discovered.

Following predecessor pointers backward reconstructs a shortest path:

Reverse that sequence to obtain the path from $s$ to $v$.

Depth-first search uses a stack

A stack is a last-in, first-out structure: the most recently inserted item leaves first. Depth-first search (DFS) uses a stack, either explicitly or through recursive function calls.

DFS follows one route as far as possible. When the current vertex has no undiscovered neighbor, it backtracks to the previous vertex and tries the next neighbor.

Using the same alphabetical adjacency order, one possible DFS discovery sequence from $A$ is

The route first dives $A\to B\to D$, backtracks to $B$, and then continues $B\to E\to F\to C$. DFS builds a valid search tree but does not generally give shortest paths. In the example, it reaches $C$ through a long tree route even though edge $AC$ exists.

DFS is useful when the shape of deep dependencies matters—for example, detecting cycles, ordering prerequisites, or exploring every branch of a puzzle. BFS is the natural choice when the number of unweighted steps matters.

Running time with adjacency lists

Chapter 5 introduced asymptotic running time. In either BFS or DFS, every vertex is discovered at most once. With adjacency lists, every undirected edge appears in two neighbor lists, so it is inspected at most twice. Therefore

With an adjacency matrix, inspecting all possible neighbors of every reached vertex can take $O(|V|^2)$ time, even for a sparse graph. The representation affects the algorithm's cost.

Run BFS and DFS explorers through the same network. Predict the next processed vertex, inspect the live queue or stack, replay backtracking, and compare the two search trees and discovered routes.

Weighted shortest paths need accumulated cost

BFS minimizes the number of edges. It does not minimize total weight when edges have different costs. A two-edge route of weights $2$ and $3$ costs $5$, while a one-edge route of weight $9$ costs $9$.

For a weighted path

define its total weight by

The weighted distance from $s$ to $v$ is the minimum $w(P)$ over all $s$-to-$v$ paths.

Tentative distances and relaxation

Dijkstra's algorithm solves the single-source shortest-path problem when every edge weight is nonnegative.

It maintains a tentative distance $d[v]$, the best path cost to $v$ found so far. Initially,

Suppose the algorithm knows a route to $u$ of cost $d[u]$ and inspects edge $uv$. Traveling through $u$ would give a route to $v$ of cost $d[u]+w(uv)$. The update

is called relaxing edge $uv$. If the second value is smaller, also set $\operatorname{pred}(v)=u$.

Dijkstra's settled frontier

A vertex is settled when its tentative distance is declared final. Dijkstra repeats:

1. choose the unsettled vertex $u$ with the smallest $d[u]$;

2. settle $u$;

3. relax every edge from $u$ to an unsettled neighbor;

4. stop when every reachable vertex is settled, or when the desired target is settled.

For edges

start at $A$. First settle $A$, giving $d[B]=4$ and $d[C]=1$. Settle $C$ next; relaxing $CB$ improves $d[B]$ from $4$ to $3$, and $CD$ gives $d[D]=6$. Settle $B$ next; $BD$ improves $d[D]$ from $6$ to $4$. Then settle $D$ and obtain $d[E]=7$.

The predecessor chain for $E$ is

so a shortest path is $A,C,B,D,E$ with total weight $1+2+1+3=7$.

Why nonnegative weights matter

When Dijkstra settles the smallest tentative distance $d[u]$, every unsettled route must first reach some unsettled vertex with tentative cost at least $d[u]$. Nonnegative remaining edges cannot reduce that cost below $d[u]$.

A negative edge breaks this reasoning. A route discovered later might use a negative weight to become cheaper than an already settled route. Dijkstra's algorithm must therefore reject graphs with negative edge weights. Other algorithms can handle some negative-weight graphs, but they are beyond this section.

A simple array implementation scans all vertices to find the smallest unsettled tentative distance and runs in $O(|V|^2)$ time. A priority queue is a structure that removes the item with the smallest key; using one can avoid scanning every vertex on sparse graphs.

Dispatch weighted rescue routes by choosing which tentative vertex to settle and which edges to relax. The map preserves old and improved labels, reconstructs the predecessor route, and includes a negative-edge incident that exposes exactly why Dijkstra's guarantee fails.

Choosing the right search

Use BFS to minimize the number of edges in an unweighted graph. Use DFS to explore deeply, backtrack, and reveal structural dependencies. Use Dijkstra to minimize accumulated nonnegative edge weight.

Section 11.4 changes the scale of the optimization. Instead of finding one shortest route, it asks which set of edges connects every vertex with no redundancy and, in a weighted graph, with the least total cost.