Breadth-first search

What this chapter covers

Breadth-first search is the graph traversal that explores outward in rings — everything one step away, then everything two steps away, and so on. Its engine is the queue from the linear-structures tier, and that FIFO discipline gives BFS a superpower: the first time it reaches any node, it has reached it by the fewest possible edges. So BFS isn't just a way to visit every reachable node; on an unweighted graph it's the shortest-path algorithm — the one behind "degrees of separation," maze solvers, and "fewest moves" puzzles. This chapter builds it, watches the frontier expand in waves, and shows it finding paths an order of magnitude shorter than a depth-first search would.

A bit of history

Breadth-first search was invented several times for practical routing problems. Konrad Zuse described it in 1945 in his unpublished thesis, but the versions that stuck came from engineering: Edward Moore published it in 1959 as a method for finding the shortest path through a maze, and C. Y. Lee independently developed it in 1961 for routing wires on circuit boards — the "Lee algorithm" still used in chip design. That origin is telling: BFS wasn't a theoretical curiosity but a tool for finding shortest connections in physical networks, mazes and circuits, which is exactly what it's still best at. Its pairing with the queue, and its guarantee of shortest paths, made it one of the two foundational graph traversals, and the template — explore a frontier, mark what you've seen, expand outward — recurs in Dijkstra, A*, and half the algorithms in this tier.

The intuition

Start at a node and put it in a queue. Now repeat: take the node at the front of the queue, and for each of its neighbors you haven't seen before, mark it seen and add it to the back of the queue. Because the queue is first-in-first-out, you process nodes in the exact order you discovered them — which means all the start's immediate neighbors (distance 1) come out before any of their neighbors (distance 2), which come out before distance 3, and so on. BFS sweeps the graph in concentric rings of distance.

That ordering is where the shortest-path guarantee comes from. The first time BFS reaches a node, it must be via a shortest path, because BFS explores all shorter distances before longer ones — there's no way to reach a node in fewer steps than the ring it first appears in. Record each node's discoverer (its "parent") and you can walk those parents back from any target to recover the actual shortest path.

Complexity: how it scales

BFS is $O(V + E)$ time: every vertex is enqueued and dequeued exactly once, and every edge is examined once (when its source is processed). Space is $O(V)$ for the queue and the visited/ distance markers. This linear cost is because it runs on an adjacency list — on a matrix, finding each node's neighbors would cost O(V), making the whole thing O(V²). The face-off doesn't race speed (both traversals are O(V+E)); it races the quality of the path each finds, because that's what distinguishes them:

On 400-vertex random graphs, BFS found paths averaging 5.2 edges, while DFS found paths averaging 53 — more than 10 times longer, for the same source and target. That gap is the whole point: both traversals reach the target, but only BFS reaches it optimally. DFS's path is a path, wandering down whatever branch it happened to take; BFS's is the shortest. When "fewest steps" matters, this is the difference between a right answer and a merely valid one.

What it's good at, what it isn't

BFS is the right tool for shortest paths in unweighted graphs and anything shaped like "fewest steps": maze solving, word-ladder puzzles, degrees of separation in a social network, the minimum number of moves in a game, nearest-first exploration. It's also the natural choice whenever you want to process a graph level by level, or find the closest node satisfying some condition, since it reaches near things before far things. And it's simple, linear, and guaranteed optimal for these problems.

Where BFS stops being optimal is weighted graphs. The moment edges have different costs — a road network where roads have lengths, a network where links have latencies — "fewest edges" is no longer "shortest distance," and BFS's guarantee evaporates: the fewest-hops route can be far longer than a many-hops route made of short edges. That's the problem Dijkstra's algorithm solves, later in the tier, by replacing BFS's plain queue with a priority queue. BFS also uses O(V) memory for its frontier, which on very wide graphs can be a lot; DFS's stack is often shallower. For unweighted shortest paths, though, BFS is exactly right.

The data, or the inputs

The face-off runs BFS and DFS on random graphs and compares the length of the path each finds between random pairs, isolating BFS's shortest-path optimality. The animation runs BFS on a small grid graph from the top-left corner, so you can watch the frontier expand in clean rings of distance.

Build it, one function at a time

The core traversal — a queue, marking distance on discovery:

def bfs(adj, start, probe=None):
    """Explore the graph breadth-first from `start` using a QUEUE. Mark a node's distance
    the moment it's discovered and enqueue it; process the queue front to back. Every node
    is enqueued once, and its recorded distance is the shortest (fewest-edge) distance from
    the start. O(V + E): each vertex and edge is touched once. Returns the visit order and
    the distance array."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        if probe is not None:
            probe.append({"node": u, "dist": dist[u], "frontier": list(q)})
        for v in adj[u]:
            if dist[v] == -1:              # first time we've seen v → this is its shortest distance
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

And shortest-path reconstruction — the same BFS remembering parents, then walking them back:

def shortest_path(adj, start, target):
    """Reconstruct a shortest (fewest-edge) path. Same BFS, but remember each node's parent
    (who discovered it); then walk parents back from the target. This is how BFS powers
    maze solving, social 'degrees of separation', and any unweighted shortest path."""
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    if dist[target] == -1:
        return None                        # target unreachable
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]

Watch it work

Here's BFS exploring a 2×4 grid from node 0. Orange is the node being processed right now; blue nodes are the frontier (discovered, waiting in the queue); green nodes are done; dark nodes are undiscovered. Step through it and watch the wave: from 0, it discovers its neighbors 1 and 4 (distance 1) and queues them; then it processes those, discovering distance-2 nodes; and so on. The blue frontier is always exactly the ring at the current distance, sweeping outward. Because that ring reaches near nodes before far ones, every node's first discovery is along a shortest path — the guarantee, made visible:

The complete code

Both versions in one place — flip between them. The from-scratch tab is BFS and its shortest- path reconstruction. The library tab is the DFS it's compared against — the traversal that visits everything too but doesn't find shortest paths — plus a plain BFS reference. (The real graph library is networkx; Python has no built-in graph traversal.)

"""Breadth-first search — the graph traversal that explores in waves of increasing
distance from the start, and the first algorithm most graph problems reduce to.

Its engine is the queue from the linear-structures tier. Because a queue serves nodes in
the order they were discovered (first in, first out), BFS finishes everything one edge
away before it touches anything two edges away, and so on outward. That ordering has a
powerful consequence: the first time BFS reaches a node, it has reached it by a SHORTEST
path — the fewest edges possible. So BFS isn't just a way to visit every node; on an
unweighted graph it's the shortest-path algorithm.
"""
from collections import deque


# region: bfs
def bfs(adj, start, probe=None):
    """Explore the graph breadth-first from `start` using a QUEUE. Mark a node's distance
    the moment it's discovered and enqueue it; process the queue front to back. Every node
    is enqueued once, and its recorded distance is the shortest (fewest-edge) distance from
    the start. O(V + E): each vertex and edge is touched once. Returns the visit order and
    the distance array."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        if probe is not None:
            probe.append({"node": u, "dist": dist[u], "frontier": list(q)})
        for v in adj[u]:
            if dist[v] == -1:              # first time we've seen v → this is its shortest distance
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist
# endregion


# region: shortest_path
def shortest_path(adj, start, target):
    """Reconstruct a shortest (fewest-edge) path. Same BFS, but remember each node's parent
    (who discovered it); then walk parents back from the target. This is how BFS powers
    maze solving, social 'degrees of separation', and any unweighted shortest path."""
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    if dist[target] == -1:
        return None                        # target unreachable
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]
# endregion

"""The graph library is the third-party `networkx` (`nx.shortest_path`, `nx.bfs_edges`) —
no graph traversal in the standard library. To show what makes BFS special rather than just
correct, the counterpart here is depth-first search (next chapter's algorithm), which visits
every node too but does NOT find shortest paths: it plunges deep, so the path it discovers to
a node can be far longer than necessary. The face-off compares the path lengths the two
traversals find, and BFS's optimality is the point.
"""
from collections import deque


# region: dfs_path
def dfs_path(adj, start, target):
    """A path from start to target via depth-first search (an explicit stack). It finds *a*
    path if one exists, but not the shortest — DFS follows one branch as far as it goes, so
    it can reach the target by a long detour. Contrast with BFS's shortest path."""
    n = len(adj)
    visited = [False] * n
    parent = [-1] * n
    stack = [start]
    visited[start] = True
    while stack:
        u = stack.pop()
        if u == target:
            break
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)
    if not visited[target]:
        return None
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]
# endregion


# region: bfs_reference
def bfs_distances_reference(adj, start):
    """A plain BFS distance computation, as an independent reference to check against."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist
# endregion

Scratch vs library

The comparison here isn't speed — BFS and DFS are both O(V+E) — it's correctness of a different kind: the quality of the answer. DFS's paths were 10× longer than BFS's on the same graphs, which is the sharpest possible illustration that two algorithms with identical complexity can give wildly different answers to the same question. Choosing BFS over DFS for a shortest-path problem isn't an optimization; it's the difference between right and wrong. This reframes what "which algorithm" means: sometimes you choose for speed, but often, as here, you choose because one algorithm has a property the other lacks — BFS's shortest-path guarantee — and no amount of tuning gives DFS that property. Match the algorithm to the guarantee you need, not just the time bound.

Where you'll actually meet it

BFS runs anywhere "fewest steps" is the question. Social networks compute degrees of separation and friend-suggestion distances with it. GPS and games use it for shortest paths on unweighted grids, and it's the skeleton of the weighted pathfinders (Dijkstra, A*) that power real navigation. Web crawlers explore breadth-first to reach important nearby pages first. Network broadcast and flood-fill (the paint-bucket tool) are BFS. Garbage collectors trace reachable objects with it. Chip-design routers use Moore and Lee's original maze algorithm. And countless puzzles — Rubik's cube in fewest moves, word ladders, sliding tiles — are BFS over a state graph. Whenever you need the shortest chain of steps, BFS is the first tool to reach for.

Takeaways

Breadth-first search explores a graph in rings of increasing distance using a queue, visiting every reachable node in $O(V+E)$ and — because FIFO order reaches each node by the fewest edges first — finding shortest paths in unweighted graphs. Its shortest-path guarantee, not its speed, is what makes it the right choice, and it comes entirely from the queue: swap in a stack and you get depth-first search, deepest-first instead of nearest-first.

That stack-based sibling is the next chapter. Depth-first search plunges down each branch to its end before backtracking, which makes it worse at shortest paths but better at a different set of questions — detecting cycles, ordering dependencies, finding connected components and articulation points. Between BFS's breadth and DFS's depth, you have the two lenses through which every graph algorithm in this tier views a graph.