Breadth-first search

How breadth-first search works

Step by step

1. Start at A: mark it seen, set distance 0, enqueue it. The queue is the frontier - discovered but not yet processed.
2. Dequeue A and scan its neighbours. B and D are new: mark both immediately, record distance 1, and push them to the back.
3. Dequeue B (distance 1). A is already seen and gets skipped; C and E are marked at distance 2.
4. Dequeue D. E is already marked - skipping it is what keeps the queue from growing without bound. Only G is new, at distance 2.
5. Ring 2 drains: C discovers F at distance 3, E discovers H at distance 3, G finds nothing new.
6. The queue empties after visiting all 8 nodes in order A, B, D, C, E, G, F, H. Every recorded distance is the true shortest hop count.

Complexity

Reference implementation

from collections import deque

def bfs(adj, start):
    seen = {start}
    dist = {start: 0}
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)          # mark when enqueued, not when visited -
                dist[v] = dist[u] + 1 # otherwise a node can enter twice
                q.append(v)
    return order, dist

function bfs(adj, start) {
  const seen = new Set([start]);
  const dist = new Map([[start, 0]]);
  const q = [start];
  const order = [];
  for (let head = 0; head < q.length; head++) {   // index instead of shift()
    const u = q[head];
    order.push(u);
    for (const v of adj.get(u) ?? []) {
      if (!seen.has(v)) {
        seen.add(v);
        dist.set(v, dist.get(u) + 1);
        q.push(v);
      }
    }
  }
  return { order, dist };
}

static Map<String,Integer> bfs(Map<String,List<String>> adj, String start) {
    Map<String,Integer> dist = new HashMap<>();
    Deque<String> q = new ArrayDeque<>();
    dist.put(start, 0);
    q.add(start);
    while (!q.isEmpty()) {
        String u = q.poll();
        for (String v : adj.getOrDefault(u, List.of())) {
            if (!dist.containsKey(v)) {
                dist.put(v, dist.get(u) + 1);
                q.add(v);
            }
        }
    }
    return dist;
}

Common pitfalls

• Marking nodes when dequeued instead of when enqueued. A node with three neighbours visited ahead of it enters the queue three times and the run stops being O(V + E) - the single most common BFS bug.
• Using BFS on weighted graphs. It counts edges, not weight, so a 2-edge path of cost 100 beats a 3-edge path of cost 3. Weights need Dijkstra.
• Calling shift() on a JavaScript array as the queue. Each shift is O(n); walk a head index forward instead, as the implementation here does.
• Forgetting BFS covers only one connected component. Nodes unreachable from the start keep distance infinity - loop over unvisited nodes if you need the whole graph.
• Reconstructing paths without parent pointers. Store parent[v] = u at discovery time; walking those pointers backwards from the target is the path, for free.

Where it is used

• Degrees of separation in social graphs - LinkedIn's 2nd and 3rd connections are literally BFS rings.
• Shortest-move puzzles in interviews: word ladder, sliding puzzle, knight moves, rotten oranges - all BFS on an implicit graph.
• Web crawlers and network broadcast, which expand outward level by level from a seed.
• Garbage collectors and flood fill, marking everything reachable from a starting point.

Frequently asked questions