Graph Traversal (BFS and DFS)
Queue-based BFS distances and stack-based DFS exploration.
The idea
A graph traversal starts from a source vertex $s$ and visits every vertex reachable from it exactly once. Both standard traversals do the same bookkeeping: discover $s$, keep a collection of vertices discovered but not yet explored, and repeatedly take one out, examine its neighbours, and discover any that are new. They differ in one decision — which discovered vertex to explore next — and that decision determines what the traversal computes.
Algorithm.
Algorithm: Breadth-First Search (BFS) Input: a graph, a source vertex s Output: every reachable vertex v, labeled with d(v), the fewest edges on any path from s to v 1. mark s discovered, d(s) = 0, put s in the queue 2. if the queue is empty, return the labels 3. take out the vertex u that has waited in the queue longest 4. for each undiscovered neighbour w of u: mark w discovered, d(w) = d(u) + 1, put w in the queue // vertices enter the queue in nondecreasing d 5. go to step 2
Breadth-first search explores the oldest discovered vertex, so its collection is a queue. Serving the oldest vertex first means BFS finishes every vertex one edge from $s$ before touching any vertex two edges away, which is why its labels are shortest-path distances in an unweighted graph. Depth-first search explores the newest instead, so its collection is a stack — equivalently, the call stack of the recursive procedure below.
Algorithm.
Algorithm: Depth-First Search (DFS) Input: a graph, a source vertex s Output: every reachable vertex, each discovered and later finished 1. mark s discovered, explore s 2. to explore u: examine its neighbours in turn if a neighbour w is undiscovered, mark w discovered and explore w by these same steps, then resume u's remaining neighbours 3. when every neighbour of u is examined, u is finished // resume the vertex whose exploration discovered u 4. when s itself is finished, stop // every reachable vertex discovered once, finished once
DFS therefore follows one path as far as it can and backtracks only when stuck. Recording when each vertex is discovered and when it is finished produces nested intervals, and those intervals reveal cycles, ancestry, and orderings consistent with the edges.
Both run in $O(V + E)$ time with adjacency lists, since each vertex is discovered once and each edge is inspected a constant number of times, and both use $O(V)$ space.
Ways to work on it
- Walkthrough. BFS distances, DFS visit order, and the queue-versus-stack distinction.
- Practice. Compute a BFS shortest-path distance on a small graph.
- Hardest. Classify the edges a DFS produces and decide whether the graph has a directed cycle.
Not sure where to start? Take the ten-question placement test.