Graph Traversal: BFS & DFS

Graph Theory

Chapter 3 · Graph Traversal: BFS & DFS

Every algorithm this course covers from here on — cycle detection, topological sort, shortest paths — is a variation on one of two ways to systematically visit every reachable vertex in a graph. Both visit the same vertices in the end; the order they visit them in is what makes each one suited to genuinely different problems.

Breadth-First Search (BFS) — Level by Level

The mechanism

BFS uses a queue (first-in, first-out): visit a vertex, add all its unvisited neighbors to the queue, then process the queue in the order they were added — visiting every vertex at distance 1 from the start before any vertex at distance 2.

Depth-First Search (DFS) — Follow One Path to the End

The mechanism

DFS uses a stack (last-in, first-out) — or, equivalently, recursion (Algorithms & Complexity Chapter 5's own recursion machinery, applied directly): visit a vertex, immediately dive into its first unvisited neighbor, and keep diving until forced to backtrack.

A Worked Comparison: Genuinely Different Orders

A branching graph: A connects to B and C; B connects to D and E; C connects to F.

Traversal	Visit order from A
BFS	`A, B, C, D, E, F` — both level-1 vertices (B, C) before any level-2 vertex
DFS	`A, B, D, E, C, F` — B's entire branch (D, E) fully explored before C is even touched

Why BFS finds the shortest path in an unweighted graph

Because BFS processes strictly level by level, the first time it reaches any vertex is guaranteed to be via the fewest possible edges — there's no way to reach a vertex "early" through a longer path, since every shorter path from the same level would have been explored first. DFS has no such guarantee: it happily commits to a long, winding path before ever backtracking to check a much shorter one.

Complexity — And Why the Representation Choice Matters

O(V+E) — on an adjacency list

Both BFS and DFS visit every vertex exactly once (O(V)) and, for each vertex, examine every one of its edges exactly once (O(E) total across the whole traversal) — Θ(V+E) altogether, using Chapter 2's own adjacency list.

The representation choice directly changes this

Using an adjacency matrix instead, finding a vertex's neighbors means scanning its entire row — O(V) per vertex — making the whole traversal O(V²), not O(V+E). For a sparse graph, this is a real, measurable slowdown, not just a storage inconvenience: Chapter 2's own representation choice propagates directly into every traversal algorithm built on top of it.

Real Use Cases

Traversal	Used for
BFS	Shortest path in unweighted graphs, "nearest" queries, level-order/web-crawling-by-distance
DFS	Cycle detection (Chapter 4), topological sort (Chapter 5), path-existence/maze-solving, finding connected components

Both Traversals in Code

from collections import deque

adj = {'A': ['B','C'], 'B': ['A','D','E'], 'C': ['A','F'],
       'D': ['B'], 'E': ['B'], 'F': ['C']}

def bfs(start):
    visited, order, q = {start}, [start], deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in visited:
                visited.add(v); order.append(v); q.append(v)
    return order

def dfs(start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start); order.append(start)
    for v in adj[start]:
        if v not in visited:
            dfs(v, visited, order)
    return order

print(bfs('A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
print(dfs('A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

Hands-On Exercises

Exercise 1

A graph has vertex 1 connected to 2 and 3; 2 connected to 4; 3 connected to 5 and 6. Trace the BFS visit order starting from vertex 1, following this chapter's own level-by-level method.

📄 View solution

Exercise 2

Using the exact same graph as Exercise 1, trace the DFS visit order starting from vertex 1 (visiting each vertex's neighbors in the order given: for vertex 1, visit 2 before 3; for vertex 3, visit 5 before 6). Compare the resulting order directly against Exercise 1's BFS order.

📄 View solution

Exercise 3

Explain, in your own words, why BFS is guaranteed to find the shortest (fewest-edge) path to every reachable vertex in an unweighted graph, while DFS gives no such guarantee — grounding your answer in this chapter's own level-by-level vs. dive-then-backtrack distinction.

📄 View solution

Chapter 3 Quick Reference

BFS: queue-based, visits level by level — guarantees the shortest (fewest-edge) path in unweighted graphs
DFS: stack/recursion-based, dives down one branch fully before backtracking
Both are Θ(V+E) on an adjacency list — but O(V²) on an adjacency matrix, since Chapter 2's own representation choice directly affects traversal speed
BFS → shortest unweighted paths, nearest-neighbor queries; DFS → cycle detection, topological sort, path existence, connected components
Next chapter: Connectivity and cycle detection