Graph BFS

TL;DR

BFS is a queue plus a visited set. You push the source, then repeatedly pop the front, look at its neighbours, and push the unseen ones onto the back. Because the queue is FIFO, you process every node at distance d from the source before you touch any node at distance d + 1 — the search expands in concentric rings.

That ordering is the whole point. On an unweighted graph (every edge cost = 1), the first time BFS dequeues a node is also the shortest-path distance to it. There’s no relaxation step, no priority queue, no need to revisit. Push, pop, mark, repeat.

If your edges have weights, BFS is wrong — use Dijkstra (non-negative weights) or Bellman-Ford (negative weights). If you only need to know whether a node is reachable and don’t care about distance, DFS is fine and uses less memory. BFS earns its keep when the question is “shortest number of steps” on a graph where every step costs the same.

The implementation is short, but three details make or break it: mark nodes visited on enqueue (not on dequeue), keep the queue as a collections.deque (not a list — pop(0) is O(n)), and decide up front whether you need per-level state, because that changes the inner loop.

When to reach for it

Signals that BFS is the right tool:

• The problem says “shortest path”, “minimum number of steps”, “fewest moves”, or “least time” on a graph or grid where each step has the same cost.
• The graph is unweighted — adjacency lists, grids with 4- or 8-connectivity, state machines where every transition is one move.
• You need a shortest path in a grid (number of islands’ shortest variant, shortest path in binary matrix, knight on a chessboard).
• The problem is a multi-source spread: rotting oranges, walls and gates, fire spreading on a grid, infection radius. Seed every source at distance 0 and run one BFS.
• The state space isn’t an explicit graph but states with one-step transitions — word ladder, open-the-lock, shortest sequence of moves to a goal configuration.

Signals it’s not BFS: weighted edges (use Dijkstra), all-pairs queries on a small dense graph (Floyd-Warshall), or you’re enumerating paths rather than finding the shortest one (DFS or backtracking).

Flavor 1 — grid BFS (shortest path in a 0/1 grid)

The canonical setup: a grid where 0 is walkable, 1 is blocked, and you want the shortest number of cells from (0, 0) to (R-1, C-1).

from collections import deque

def shortest_path(grid: list[list[int]]) -> int:
    R, C = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[R-1][C-1] == 1:
        return -1
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = {(0, 0)}
    q = deque([(0, 0, 1)])  # (row, col, distance)
    while q:
        r, c, d = q.popleft()
        if (r, c) == (R - 1, C - 1):
            return d
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Worked example. A 4x4 grid (0 = walkable, 1 = blocked):

. . 1 .
. 1 . .
. . . 1
1 . . .

As integers: [[0,0,1,0],[0,1,0,0],[0,0,0,1],[1,0,0,0]]. Source (0,0), goal (3,3).

Visited set at termination: every reachable cell that’s been enqueued. Note that (0,1) had no new neighbours because its only walkable neighbour (0,0) was already visited and (0,2) is blocked. The same skeleton solves number of islands — replace the goal check with a flood-fill that increments an island counter every time you start a fresh BFS from an unvisited 1.

Flavor 2 — multi-source BFS (rotting oranges)

When multiple sources spread in parallel — rot, fire, gate proximity — seed all of them into the queue at distance 0 and run one BFS. The result is the minimum distance from any source to each cell.

from collections import deque

def oranges_rotting(grid: list[list[int]]) -> int:
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c, 0))   # already rotten, dist 0
            elif grid[r][c] == 1:
                fresh += 1
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    elapsed = 0
    while q:
        r, c, t = q.popleft()
        elapsed = t
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                grid[nr][nc] = 2  # mark visited by mutating in place
                fresh -= 1
                q.append((nr, nc, t + 1))
    return elapsed if fresh == 0 else -1

Why this beats running BFS once per source: with k rotten oranges and n cells, per-source BFS is O(k · n). Multi-source BFS is O(n) — every cell is enqueued and dequeued exactly once, no matter how many sources you started with. The FIFO ordering still gives you minimum distance because all sources enter at distance 0, so the first time any cell is reached is from its closest source.

Same template solves walls and gates (seed every gate at 0, propagate distances into empty rooms) and 01-matrix (distance from each cell to the nearest zero — seed every zero).

Flavor 3 — word ladder (state-space BFS)

The graph isn’t given to you — you build it implicitly. Nodes are words, edges connect words that differ by exactly one character. Find the shortest transformation from begin to end, where every intermediate word must be in a dictionary.

from collections import deque

def ladder_length(begin: str, end: str, word_list: list[str]) -> int:
    words = set(word_list)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i+1:]
                if nxt in words and nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, steps + 1))
    return 0

Trace. begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"].

The path hit → hot → dot → dog → cog has length 5. The same template handles open the lock (state = 4-digit string, edges = ±1 on any wheel) and any “minimum moves to reach configuration” puzzle.

Why it works — the invariant

The correctness argument is one sentence: the first time BFS dequeues a node, it’s at minimum distance from the source.

Why? BFS processes nodes in non-decreasing order of distance. The queue contains, at any point, nodes at distance d followed by nodes at distance d + 1 — nothing else. When you pop a node v at distance d, every node already dequeued was at distance ≤ d, and every node still in the queue is at distance ≥ d. If there were a shorter path to v, BFS would have reached it through a node at distance < d - 1, which would have enqueued v earlier — contradiction.

This is why marking visited on enqueue is correct: once a node is in the queue, no future enqueue can give it a shorter distance, so re-adding it is pure waste. It’s also why BFS doesn’t generalise to weighted graphs — a longer-hop path can have lower total weight, breaking the “first dequeue = shortest” invariant.

Complexity

• Time: O(V + E). Every vertex is enqueued and dequeued once; every edge is examined once when its tail is processed.
• Space: O(V) for the visited set and the queue. The queue can hold up to a full BFS frontier, which on a grid is O(min(R, C)) and in general is O(V).

For a grid of R × C cells with 4-connectivity, V = R · C and E ≈ 2RC, so both bounds are O(RC).

Common pitfalls

• Marking visited on dequeue instead of enqueue. A node gets reached by multiple neighbours and you push duplicate copies before any of them pops. On a dense graph this blows up exponentially — visited must be set the moment the node enters the queue.
• Using a Python list as the queue. list.pop(0) is O(n), making your BFS O(V²). Always use collections.deque.
• Off-by-one on grid bounds. 0 <= nr < R not 0 <= nr <= R. Pair this with row-vs-col confusion and you’ve got a guaranteed bug. Write the bounds check once, in a helper if needed.
• Forgetting to mark the source visited. If you only mark on dequeue, the source can get re-enqueued by its own neighbour. Add the source to visited before the loop, the same moment you push it.
• Not popping levels in chunks when you need per-level state. If the problem asks for “minutes elapsed” or “depth at termination”, carry distance in the queue tuple (the templates above do this) or do an explicit for _ in range(len(q)) level loop. Mixing the two — distance tuples and level loops — leads to off-by-one distances.

Where you see this in production

• Facebook “degrees of separation” / friend distance. Computing how many hops separate two profiles is BFS on the social graph. Production versions use bidirectional BFS — search from both ends and stop when the frontiers meet, which roughly square-roots the explored set.
• Network routing flooding (RIP, OSPF LSAs). Distance-vector and link-state protocols flood updates hop by hop; the convergence wavefront is exactly a multi-source BFS over the router topology.
• Web crawler frontier expansion. A crawler with a politeness budget per host walks the link graph in BFS order so it discovers shallow, high-PageRank pages before drilling deep — Heritrix and Common Crawl’s frontier scheduler are BFS variants.
• Git reachability for git log A..B and git fetch. Git walks the commit DAG breadth-first from B, stopping when it hits ancestors of A. The same machinery powers git fsck connectivity checks and the smart-HTTP “have/want” negotiation.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• William Fiset — Graph Theory playlist — www.youtube.com — The single best free graph-theory series on YouTube.