12.3 Graph traversal and search

After representing a network as a graph, we face a practical problem: starting at one vertex, which other vertices can we reach, and how can we find a route to a target? Branches and cycles can make trying every possible route by hand slow or repetitive. We need a rule for choosing which vertex to examine next and a record of what we have already seen. This systematic exploration is a graph traversal; when we use it to find a target or answer a route question, it is also a search.

There are two basic ways to organize the exploration: breadth-first search (BFS) and depth-first search (DFS). One works outward from the start in distance layers; the other follows a branch before returning to try another. Both can find reachable vertices. Their order differs, and that difference decides which one to use for a shortest route in an unweighted graph.

This is intermediate algorithms. Review graph representations and paths. MIT OpenCourseWare's BFS and DFS lecture gives the algorithmic version.

A basic idea: reach a target without guessing routes

In the undirected graph below, start at $S$ and look for $E$. We want to know whether $E$ is reachable and, if every edge counts as one move, how few moves are needed. Routes through $A,C$ and through $B,D$ both reach $E$. A search should discover these possibilities without repeatedly wandering around a cycle or forgetting a branch. The animation follows the breadth-first choice so we can see how it finds a three-edge route.

Use Next to follow the queue, newly found vertices, and the first shortest route to $E$.

A quick tour of BFS and DFS

Breadth-first search (BFS) explores in layers: first the start, then vertices one edge away, then two edges away, and so on. Put the start in a first-in, first-out queue and mark it visited. Repeatedly remove the front vertex; for each unvisited neighbour, mark it, record its parent and distance, and add it to the back. Marking on insertion prevents the same neighbour from entering twice. When BFS first discovers a vertex in an unweighted graph, it has found a route with the fewest edges. Follow parent pointers backwards to recover that route.

Depth-first search (DFS) follows one branch as far as it can, then backtracks to try an unexplored branch. Use a last-in, first-out stack or recursion, and mark each visited vertex so a cycle does not make the search repeat forever. DFS is useful for exploring connected components, finding cycles, and ordering dependencies. Its first route to a target need not be shortest.

Both methods should follow edge direction in a directed graph. With an adjacency list and a visited set, each vertex and edge is examined only a bounded number of times, giving $O(|V|+|E|)$ work. BFS's shortest-route claim does not apply to unequal edge weights; a longer route in edges may be cheaper in distance or cost.

Application 1: shortest route in an unweighted network

Let the undirected edges be $S$–$A$, $S$–$B$, $A$–$C$, $B$–$D$, $C$–$E$, and $D$–$E$. What is the minimum number of edges from $S$ to $E$?

1. Explore layers. From $S$ at distance $0$, discover $A,B$ at $1$, then $C,D$ at $2$.
2. Reach the target. From $C$ or $D$, discover $E$ at distance $3$.
3. Give a route. $S$–$A$–$C$–$E$ uses three edges. No two-edge route exists because $E$ does not appear in the first two BFS layers.

If $C$ is processed before $D$, it becomes $E$'s parent; the alternative route through $D$ is equally short.

Application 2: explore dependencies

Directed edges $P\to Q$, $P\to R$, $Q\to S$, and $R\to T$ mean a task points to tasks depending on it. Starting at $P$ and choosing $Q$ before $R$, what order can DFS visit?

1. Follow one branch. Visit $P,Q,S$.
2. Backtrack. $S$ has no outgoing edge; return to $P$ and visit $R,T$.
3. Read the visit order. One DFS visit order is $P,Q,S,R,T$. A different neighbour order could change it, but the same reachable tasks would be found.

DFS gives a systematic exploration. A valid task schedule requires an additional dependency-ordering step.