Graph Traversal: BFS & DFS

To traverse a graph is to visit every reachable node exactly once. Two algorithms dominate, and both answer the same question — which node next? — in opposite ways.

Drop a stone in still water. The ripples spread out in rings, reaching everything one hop away before anything two hops away. That is breadth-first search: every node at distance d is visited before any node at distance d + 1. Now picture walking a hiking trail instead: you follow one path until it dead-ends, then backtrack to the last fork and try another branch. That is depth-first search: commit to one direction until you cannot continue, then unwind. Both visit everything; they differ only in order, and that difference decides what each is good for.

BFS: ring by ring

BFS runs on a queue. You enqueue the start, then repeat: take the front node, and enqueue any neighbour you have not seen. Because the queue is first-in-first-out, a whole ring drains before the next one is touched — and the first time BFS reaches a node, it has arrived by the fewest possible hops.

from collections import deque

def bfs_distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()                 # take from the front
        for nbr in graph[node]:
            if nbr not in dist:                 # first time we reach nbr...
                dist[nbr] = dist[node] + 1      # ...is via the shortest route
                queue.append(nbr)               # add to the back
    return dist

graph = {0:[1,2], 1:[0,3,4], 2:[0,5,6], 3:[1], 4:[1,5], 5:[2,4], 6:[2]}
for node, d in sorted(bfs_distances(graph, 0).items()):
    print(f"node {node}: {d} hop(s) from 0")

node 0: 0 hop(s) from 0
node 1: 1 hop(s) from 0
node 2: 1 hop(s) from 0
node 3: 2 hop(s) from 0
node 4: 2 hop(s) from 0
node 5: 2 hop(s) from 0
node 6: 2 hop(s) from 0

This is why BFS is shortest-path for unweighted graphs: fewest edges is exactly what ring-by-ring expansion finds, with no extra machinery. (The moment edges carry weights, though, BFS breaks — it counts hops, not costs — and you need Dijkstra, the next lesson.)

DFS: deep first

DFS runs on a stack — usually the call stack, through recursion. You visit a node, then dive into its first unvisited neighbour, and only when a branch is exhausted do you back up:

def dfs(graph, node, visited, order):
    visited.add(node)
    order.append(node)
    for nbr in graph[node]:
        if nbr not in visited:
            dfs(graph, nbr, visited, order)
    return order

print(dfs(graph, 0, set(), []))

[0, 1, 3, 4, 5, 2, 6]

Notice the shape: from 0 it dives 0 → 1 → 3, backs up, takes 4 → 5 → 2, and finishes 6 — one deep plunge, not a tidy ring. That deep-first order is what makes DFS the tool for cycle detection (a node reappearing in the current path is a cycle), topological sort (reverse the finish order of a DAG), and connected components (one DFS run colours one component). Both BFS and DFS are O(V + E) time and O(V) space; the practical difference is that very deep graphs can overflow recursive DFS, so an explicit stack is the safe version there.

At a glance

Neither wins outright. BFS is for “closest answer first”; DFS is for fully exploring a branch, detecting cycles, or producing an ordering. A word-ladder puzzle (turn COLD into WARM one letter at a time, fewest steps) is an unweighted shortest-path problem, so it is BFS. Resolving install order from a dependency graph is DFS topological sort.

Practice