Breadth First Search — Tech Epitome

Breadth First Search

Expand level by level, so the first time you arrive is the shortest way.

Medium14 problems

How do I recognise this pattern?

Shortest path, minimum steps, or fewest moves on an unweighted graph.
A grid where you move between adjacent cells.
"Levels", "rounds", or "minutes until everything is reached".
Spreading processes: infection, flooding, rotting, signal propagation.
The nearest node satisfying some property.

When it is the wrong tool

Edges have differing weights — BFS's distance guarantee only holds when every edge costs the same. Use Dijkstra.
You must enumerate all paths rather than find the shortest; that is DFS with backtracking.
The graph is enormous and the target is deep, where BFS's frontier consumes too much memory.

What is it?

Visit a start node, then all its neighbours, then all of theirs, using a queue. Because nodes are reached in order of distance, the first time BFS touches a node it has arrived by a shortest path. On an unweighted graph this is the shortest-path algorithm, and the level structure answers "how many steps" directly.

The core idea

Mark a node as visited when you enqueue it, not when you dequeue it. Marking on dequeue lets the same node enter the queue several times, which quietly degrades the complexity.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1from collections import deque2 3 4def shortest_steps(start, is_goal, neighbours):5    queue = deque([start])6    visited = {start}7    steps = 08 9    while queue:10        # Draining exactly one level per iteration is what makes 'steps'11        # meaningful; without it you cannot tell levels apart.12        for _ in range(len(queue)):13            node = queue.popleft()14            if is_goal(node):15                return steps16 17            for nxt in neighbours(node):18                if nxt not in visited:19                    visited.add(nxt)   # mark on ENQUEUE, not on dequeue20                    queue.append(nxt)21 22        steps += 123 24    return -125 26 27def grid_bfs(grid, start):28    rows, cols = len(grid), len(grid[0])29    queue = deque([start])30    seen = {start}31 32    while queue:33        r, c = queue.popleft()34        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):35            nr, nc = r + dr, c + dc36            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:37                seen.add((nr, nc))38                queue.append((nr, nc))

Common mistakes

Marking visited on dequeue, which allows duplicates in the queue and can blow up the running time.
Using a list with `pop(0)` instead of a deque, making each removal O(n).
Forgetting the level-size loop when the answer is a distance rather than reachability.
Applying BFS to a weighted graph and trusting the result.

Problems using Breadth First Search

Problem	Difficulty	Role
Paint Bucket Region#91	Easy	Primary
Unlock Every Vault#93	Easy	Related
Is There a Route?#95	Easy	Related