Breadth-First Search on Graphs and Grids

Intuition

Picture a fire starting at the source vertex. Every minute it spreads along every edge to all neighbors that are not burning yet. The vertices that catch fire at minute k are exactly those at distance k. BFS simulates this with a FIFO queue: everything at distance k leaves the queue before anything at distance k + 1, so the first time a vertex is reached, it is reached by a path with the fewest edges.

Recording who discovered each vertex gives a BFS tree; walking parent pointers back from any vertex yields one shortest path.

The guarantee only holds when every edge has the same cost. With costs 0 and 1 a deque still works (0-1 BFS, below); with arbitrary non-negative weights you need Dijkstra.

When to use it in interviews / OAs

• "Minimum number of moves / steps / operations / transformations": knight moves, open the lock, word ladder, sliding puzzle. The graph is often implicit: a state is a vertex, a legal move is an edge.
• Shortest path in an unweighted grid or maze.
• "Every minute X spreads to its neighbors": rotting oranges, fire, infection. Start from all sources at once (multi-source BFS).
• "Distance from every cell to the nearest Y": 01 matrix, walls and gates. Again multi-source, from the Y cells.
• Moves that are sometimes free and sometimes cost 1 (remove an obstacle, change an arrow's direction): 0-1 BFS.
• Level-order processing of trees and graphs.

Template

Distances and one shortest path

from collections import deque


def bfs(adj: list[list[int]], src: int) -> tuple[list[int], list[int]]:
    n = len(adj)
    dist = [-1] * n  # -1 = not reached yet
    parent = [-1] * n
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:  # first visit is the shortest
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent


def path_to(parent: list[int], target: int) -> list[int]:
    # call only when target was reached
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

Shortest path in a grid

def grid_shortest_path(grid: list[str], start: tuple[int, int], goal: tuple[int, int]) -> int:
    rows, cols = len(grid), len(grid[0])
    (sr, sc), (gr, gc) = start, goal
    if grid[sr][sc] == "#" or grid[gr][gc] == "#":
        return -1
    dist = [[-1] * cols for _ in range(rows)]
    dist[sr][sc] = 0
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        if (r, c) == (gr, gc):
            return dist[r][c]  # safe to stop: nothing later in the queue is closer
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return -1

Multi-source BFS, one layer at a time

Put every source in the queue at distance 0 before the loop starts. When the question counts "minutes", process the queue one layer at a time.

def minutes_to_rot(grid: list[list[int]]) -> int:
    # 0 = empty, 1 = fresh, 2 = rotten; rot spreads to 4 neighbors each minute
    rows, cols = len(grid), len(grid[0])
    grid = [row[:] for row in grid]  # do not mutate the caller's grid
    q = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):  # exactly one layer = one minute
            r, c = q.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

0-1 BFS

If every edge costs 0 or 1, push the endpoint of a 0-edge to the front of a deque and the endpoint of a 1-edge to the back. The deque then stays sorted by distance, exactly like Dijkstra's heap but in O(1) per operation.

def zero_one_bfs(adj: list[list[tuple[int, int]]], src: int) -> list[float]:
    dist = [float("inf")] * len(adj)
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:  # w is 0 or 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

A vertex can enter the deque more than once here, so relax by comparing distances instead of using a visited flag.

Complexity

Plain, multi-source and 0-1 BFS all run in O(n + m) time and O(n) space; on an R x C grid that is O(R * C). For implicit state graphs, n is the number of reachable states, which is where the real cost hides (a 4-digit lock has 10^4 states; a 3x3 sliding puzzle has 9!/2 reachable ones).

Common pitfalls

• Marking on dequeue instead of enqueue. The same vertex gets queued many times; on dense graphs or grids this can explode. Set dist when you push.
• list.pop(0) is O(n). Use collections.deque.
• Using BFS on weighted edges. BFS minimizes the number of edges, not their total weight. Weights 0/1: 0-1 BFS. Otherwise: Dijkstra.
• A visited flag in 0-1 BFS. A vertex first reached through a 1-edge may later be improved through a 0-edge; compare distances instead.
• Multi-source done as many single-source runs. Running BFS from each source is k times slower; seed the queue with all of them instead.
• Off-by-one in "minutes". Count a minute only for a layer that actually changes something, and check the case with no fresh cells at all (answer 0).
• Forgetting blocked start or goal cells, or start == goal (answer 0).

Interview variations

• State-space BFS. Word ladder (bucket words by wildcard patterns), open the lock (skip deadends), sliding puzzle (encode the board as a string), minimum genetic mutation.
• Extra state in the vertex. "Shortest path with at most k obstacle removals" or "collect all keys" make the vertex (cell, k) or (cell, keys_mask).
• Two BFS runs. An edge (u, v) lies on some shortest a -> b path iff da[u] + 1 + db[v] == da[b]; a vertex does iff da[v] + db[v] == da[b].
• Shortest bridge between two islands. DFS marks one island, then multi-source BFS from all its cells until the other island is touched.
• Bidirectional BFS. Expand from both ends, always the smaller frontier; it shrinks huge state spaces (word ladder with long dictionaries).
• BFS over groups instead of vertices. "Bus routes": the vertices are routes, so each route is expanded once.