Graphs II — BFS & Shortest Path

Review boundary and corrected contracts

BFS certifies minimum edge count for unit-cost edges. All sources start at distance zero and are marked before enqueue. The open-grid template has no obstacle test; rotting-oranges supplies its own traversability predicate. Word-ladder wildcard slicing/hashing is O(N·L²) preprocessing in straightforward Python.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Write BFS with a deque from memory, understand exactly why level order equals shortest path when all edges cost the same, and reach for multi-source BFS the moment a problem says 'nearest'.

Series: LeetCode — From Basics to Production-Ready · Session 28 / 65 · Phase 1 · Core patterns

Why this session exists

Ordinary DFS finds a path, not necessarily a shortest one. BFS certifies the fewest edges in an unweighted graph by using a FIFO queue. Exhaustive path enumeration with DFS can also find a minimum, but loses the linear-time traversal guarantee; the distinction is the invariant, not what is possible at any level of cleverness.

The genuinely elegant idea in this session is multi-source BFS. When a problem asks "for every cell, how far is the nearest zero" or "how many minutes until every orange rots", the instinct is to run a BFS from each source and take the minimum. That is O(sources × cells) and it times out. The better answer is to push all sources into the queue before the loop starts, at distance zero. The frontier then expands from all of them simultaneously, and the first time any cell is reached, it is reached by its nearest source. One sweep, O(cells), no per-source loop.

That trick — seed the queue with everything — is the reason this session exists as its own unit. It is the difference between a solution that passes and one that does not, and it looks like nothing when you read it.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

from collections import deque
q = deque(sources)     — push ALL sources first
while q: ...           — level-by-level with a for-range over len(q)

Concretely: given a grid and a list of starting coordinates, write a BFS that computes the distance from the nearest start to every reachable cell.

The three things that wobble from memory: using list.pop(0) instead of deque.popleft(), marking visited on pop instead of on push, and forgetting that all sources go in before the loop begins. Any of those is today's finding.

Pattern anatomy

The shape of problem that summons BFS: uniform-cost expansion where the question is how far, how many steps, or how many rounds. The critical word is uniform. Every edge must cost the same. With unequal weights, ordinary BFS no longer certifies minimum cost. Use Dijkstra for non-negative weights, 0–1 BFS for weights restricted to 0 and 1, or a suitable negative-edge algorithm when needed.

The invariant is the whole reason BFS works: the queue always holds nodes in non-decreasing order of distance from the source set. Because you only ever append nodes at distance d + 1 while popping nodes at distance d, the queue never contains a node whose distance is smaller than one already popped. Therefore the first time a node is dequeued, no shorter route to it exists.

The templates take a reusable sequence of distinct source vertices, all present in adj; each vertex has an adjacency entry, even if empty. A one-shot generator would be consumed while creating dist or seen, before queue construction. Materialize and deduplicate such an iterable first. Learn this shape:

from collections import deque
 
def bfs(adj, sources):
    dist = {s: 0 for s in sources}
    q = deque(sources)                 # ALL sources seeded at distance 0
    while q:
        node = q.popleft()
        for nxt in adj[node]:
            if nxt not in dist:        # 'not in dist' doubles as the visited check
                dist[nxt] = dist[node] + 1
                q.append(nxt)          # mark on PUSH, not on pop
    return dist

When you need explicit levels — "how many rounds until everything is done" — use the level-batching form:

def bfs_levels(adj, sources):
    seen = set(sources)
    q = deque(sources)
    level = 0
    while q:
        for _ in range(len(q)):        # snapshot the size: this is one whole level
            node = q.popleft()
            for nxt in adj[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        level += 1                     # only after the full level drains
    return level - 1                   # levels counted, minus the initial one

bfs_levels returns the greatest finite distance from the source set. With no sources it returns −1 as a sentinel, not a distance; bfs returns an empty map.

for _ in range(len(q)) is the line that matters. Python evaluates len(q) once, before the loop body starts appending, so the range is fixed to the current level's size. That is what makes the batching correct.

The grid version assumes a nonempty rectangular grid and distinct in-bounds sources. It treats every cell as traversable regardless of its stored value; add the problem-specific obstacle predicate before marking a neighbour when that is not the intended graph:

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
 
def grid_bfs(grid, sources):
    R, C = len(grid), len(grid[0])
    dist = [[-1] * C for _ in range(R)]
    q = deque()
    for r, c in sources:
        dist[r][c] = 0
        q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

The dist matrix initialised to −1 does triple duty: distance storage, visited marker, and unreachable indicator. Three responsibilities, one array, no separate set.

The cue

You are looking at a BFS problem when the statement contains one of these tells:

1. "Minimum number of steps / moves / transformations / mutations" in a setting where every step costs the same. Word Ladder, Open the Lock, Minimum Genetic Mutation. All the same problem with a different neighbour function.
2. "Nearest" or "closest" for every cell. 01 Matrix and Walls and Gates are multi-source signals: seed every zero or gate at once. Shortest Distance from All Buildings instead minimizes the SUM of distances to all buildings and requires reachability from every building; a nearest-source sweep loses that information. For two buildings at opposite ends of a three-cell line, the middle cell has nearest distance 1 but total distance 2.
3. "How many rounds / minutes / iterations until X spreads everywhere". Rotting Oranges, Infection spread. Level-batched BFS, and the answer is the level count.
4. "Shortest path in an unweighted graph." Said outright. If unequal costs matter, ordinary FIFO BFS is not the cost-minimizing algorithm; check the weight domain before choosing its replacement.
5. A state space you can enumerate with a defined transition. Lock combinations, board configurations, word transformations. The "graph" is never given; you generate neighbours from the current state on demand.

Tell 5 is the one people miss. In Word Ladder there is no adjacency list anywhere in the input. The graph is implicit: nodes are words, and two words are adjacent if they differ in exactly one letter. Recognising that a state space is a graph is the same leap as recognising that a grid is a graph.

The negative cue: if edges have different weights, ordinary BFS can give a wrong minimum-cost answer that looks plausible. It will find a path with the fewest edges, which is not the cheapest path. That distinction has cost people offers.

Guided solve

Rotting Oranges. A grid of 0 (empty), 1 (fresh orange), 2 (rotten orange). Every minute, any fresh orange orthogonally adjacent to a rotten one becomes rotten. Return the minutes until no fresh orange remains, or −1 if impossible.

Name the graph first. Nodes: grid cells. Edges: orthogonal adjacency. But the key observation is about time: all currently-rotten oranges rot their neighbours simultaneously. That simultaneity is exactly what a level-batched multi-source BFS models. Minute k corresponds to BFS level k.

So the shape is: seed the queue with every initially-rotten orange, count fresh oranges as you scan, then drain level by level.

from collections import deque
 
def orangesRotting(grid):
    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))
            elif grid[r][c] == 1:
                fresh += 1
 
    if fresh == 0:
        return 0                        # nothing to rot: zero minutes, not -1
 
    minutes = 0
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while q and fresh > 0:
        for _ in range(len(q)):
            r, c = q.popleft()
            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
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
 
    return minutes if fresh == 0 else -1

Three decisions worth defending out loud.

Why the initial scan does two jobs. One pass collects the sources and counts the fresh oranges. The fresh counter is what lets you answer the −1 case without a second full scan at the end: if any fresh orange survives the BFS, it was unreachable from every rotten source.

Why while q and fresh > 0 rather than just while q. Without the fresh condition you drain one extra level after the last orange rots — the final rotten cells get dequeued, find no fresh neighbours, and minutes increments anyway. That off-by-one gives you an answer one higher than correct, which passes the trivial cases and fails the real ones.

Why the fresh == 0 early return. It documents the zero-minute case, but it is redundant in this exact implementation: while q and fresh > 0 already skips the loop whenever there are no fresh oranges, even if rotten ones exist. Removing only the early return still returns 0 for [[2]]. Changing the loop to while q is a different mutation, which can count a useless final level. The function intentionally changes fresh cells to 2 in the caller’s nonempty rectangular grid.

Trace on [[2,1,1],[1,1,0],[0,1,1]]. Sources: (0,0). Fresh: 6. Level 1 rots (0,1) and (1,0) — fresh 4. Level 2 rots (0,2) and (1,1) — fresh 2. Level 3 rots (2,1) — fresh 1. Level 4 rots (2,2) — fresh 0, loop exits. Answer 4.

If you find yourself writing a for source in sources: bfs(source) loop and taking the minimum, stop. That is the signal that you want multi-source BFS instead. Push every source into the queue at distance zero before the main loop, and the single sweep computes the same minima in one pass. This is the highest-leverage rewrite in the entire graph section.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• 01 Matrix — for each cell, the distance to the nearest 0. Ask yourself which cells belong in the initial queue: the zeros, or the ones? Pick the wrong set and the problem becomes far harder than it is.
• Word Ladder — the graph is never given. Think about how to generate neighbours of a word cheaply; the naive "compare against every word in the list" is O(N·L) per expansion and there is a wildcard-bucket trick that beats it.

If both land early, do Open the Lock. Same state-space BFS, and the deadends set is a visited pre-seed rather than a separate check.

Common failure modes

Marking visited on pop instead of on push. If you only mark when dequeuing, the same node can be appended many times before its first pop, and the queue blows up. In dense grids this turns O(V) into something much worse and occasionally TLEs. Mark the instant you append.

Using list.pop(0) instead of deque.popleft(). pop(0) on a Python list is O(n) because every remaining element shifts left. That silently converts your O(V + E) BFS into O(V²). No wrong answer, just a timeout you cannot explain.

Incrementing the level counter inside the inner loop. The level increment belongs after the entire for _ in range(len(q)) batch drains. Inside, you count nodes rather than levels.

Recomputing len(q) inside the batch loop. With i incremented per pop, while i < len(q) can consume part of the next level or stop before finishing the current one. For queue [a,b] with neither node adding neighbours, popping a leaves length 1 and i=1, so the batch wrongly stops before b. The error is a moving boundary, not a universal result of 1.

Running single-source BFS in a loop for a nearest-X problem. Correct answer, wrong complexity. It passes the samples and TLEs on the large case.

Applying ordinary BFS to unequal-cost edges. Guarantees the fewest-edges path, not necessarily the cheapest path. There is no error and the output looks reasonable, which is what makes it dangerous.

Myth: DFS and BFS both explore the whole graph, so either one can find the shortest path — BFS is just a different traversal order.

Why: They explore the same set of nodes, but only BFS explores them in non-decreasing distance order, and that ordering is the entire source of the shortest-path guarantee. DFS commits to one branch and may reach a node via a long detour before ever finding the short route; when it later finds a shorter path it must overwrite and re-explore, which is no longer a simple traversal. The queue is not a stylistic choice — it is the proof. Swap it for a stack and the guarantee evaporates.

Steps 1: Because every edge in an unweighted graph costs exactly 1, the distance to a node is simply the number of edges on the path used to reach it.

Steps 2: Because a FIFO queue pops in insertion order, and nodes at distance d are always inserted before any node at distance d+1, the queue holds distances in non-decreasing order.

Steps 3: Because of that ordering, the first time a node is dequeued there can be no shorter path to it — any shorter path would have placed it in the queue earlier.

Steps 4: Because seeding the queue with several sources at distance 0 keeps the ordering property intact, the first arrival at a node is its distance to the NEAREST source, not to a specific one.

Steps 5: Because each node is enqueued at most once and each edge inspected at most twice, the whole sweep is O(V + E) regardless of how many sources were seeded.

Steps 6: Therefore the testable prediction is that multi-source BFS over k sources costs the same as single-source BFS on the same graph — running 01 Matrix with 1 zero and with 10,000 zeros should take the same order of time, whereas the loop-over-sources approach scales linearly in the number of zeros.

Picture: Drop stones into a pond at several points at once. The ripples expand at identical speed and stop where they meet. The moment a ripple touches a leaf, the count of rings that have passed is that leaf's distance from the nearest stone.

Trigger: Fires on the words minimum steps, fewest moves, nearest, or how many rounds — provided every move costs the same.

Name: BFS

Gain: Guarantees the shortest path in unweighted graphs; natural level semantics for 'rounds'; iterative so no stack-depth risk

Cost: Queue can contain the rest of one distance layer and part of the next; in general it needs O(V) space, as when every grid cell is a source

Name: DFS

Gain: O(depth) recursive stack; useful for reachability, components and cycle detection. A general graph still needs O(V) visited state

Cost: A plain DFS traversal gives no fewest-edge guarantee; exhaustive path search is not the same linear-time algorithm

Name: Dijkstra

Gain: Correct on non-negative weighted edges

Cost: A heap-based implementation commonly costs O((V+E) log V); its priority queue is unnecessary for uniform positive weights, though no universal wall-clock comparison follows

Pick: BFS when the answer is a count of steps and every edge costs 1. DFS when the answer is 'can I reach it', 'how many components', or 'is there a cycle'. Dijkstra only when the edges carry different non-negative weights — if a candidate reaches for Dijkstra on a uniform grid, that is a signal they do not know why BFS works.

Complexity

Time: O(V + E). Each node is enqueued at most once, because the visited mark is written at push time. Each dequeue examines that node's adjacency list once, so every edge is inspected at most twice in an undirected graph. On a grid, V = m·n and each cell has at most four neighbours, giving O(m·n) — linear in cells.

Multi-source changes nothing asymptotically. Seeding k sources costs O(k) up front, and k ≤ V, so it disappears into the O(V) term. This is the key result: BFS from 10,000 sources costs the same as BFS from 1.

Space: O(V). The queue straddles at most two consecutive distance layers, and the visited/distance structure holds up to V entries. Multiple sources can initially fill the entire m×n grid queue, so O(min(m,n)) is not a valid general queue bound. The distance matrix alone takes O(m·n).

For Word Ladder, building L wildcard strings of length L for each of N words costs O(N·L²) time and up to O(N·L²) character storage in straightforward Python. During BFS, scan each bucket only the first time it is encountered, then clear it: its words have all been discovered at the earliest possible distance. This bounds total bucket-entry visits by O(N·L), while pattern construction across expansions costs O(N·L²). Without clearing, repeated scans cost the sum of squared bucket sizes, so the claimed overall bound needs either bucket clearing or an explicit fixed-alphabet bound. A word’s expansion costs O(L² + sum of scanned bucket sizes), not just O(L·bucket size).

Self-check (answer follows each question).

Q: Why does BFS give the shortest path in an unweighted graph while DFS does not?

A: BFS pops nodes in non-decreasing distance order because it appends distance-d+1 nodes only while draining distance-d nodes. So the first dequeue of a node is via a shortest path. DFS commits depth-first and can reach a node by a long detour first, with no ordering guarantee.

Q: What breaks if you mark nodes visited when you pop rather than when you push?

A: The same node can be appended multiple times before its first pop, inflating the queue and the work done. The answer usually stays correct but the complexity degrades and can time out.

Q: In level-batched BFS, why is for _ in range(len(q)) correct but while i < len(q) wrong?

A: range(len(q)) snapshots the initial length, so the batch is exactly the current level. A moving length can mix levels or end a batch early: two queued leaf nodes become two batches if the loop compares its incrementing counter with the shrinking queue length.

Q: For 01 Matrix, which cells go into the initial queue and why?

A: The zeros, seeded at distance 0. The undirected grid distance is symmetric, so distances FROM zeros are the desired distances TO a nearest zero. Seeding all ones would instead compute distance to a nearest one, which is a different query.

Q: What is the complexity difference between multi-source BFS and looping single-source BFS over k sources?

A: Multi-source is O(V + E) total; k independent sweeps have worst-case cost O(k·(V + E)). Taking the minimum gives the same nearest-source distances, but the repeated work may exceed a problem’s time budget. These bounds do not predict a specific timeout.

Q: Word Ladder has no adjacency list in the input. How do you generate neighbours without comparing every word against every other word, and what does that cost?

A: Map wildcard patterns to word lists: 'hot' goes under *ot, h*t and ho*. Building the map costs O(N·L²) for Python string construction and hashing. Each expansion costs O(L² + total entries in the buckets it scans). Clear a bucket after its first scan so all bucket entries are scanned only O(N·L) times overall; otherwise include repeated bucket-scan costs. Pairwise comparison instead costs O(N·L) per expansion.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Rotting Oranges enters the queue today. If you wrote the level increment in the wrong place or used pop(0), that is failed even if the final submission was accepted — the queue tracks what came out of cold memory, not what came out after debugging.

• The queue is the proof. BFS pops in non-decreasing distance order, and that ordering is the entire shortest-path guarantee — a stack destroys it.

• Multi-source BFS: push every source at distance 0 before the loop. Same O(V + E) bound, without the multiplicative cost of independent per-source sweeps.

• Mark visited on push, never on pop. Marking on pop lets duplicates accumulate in the queue.

• deque.popleft() is O(1); list.pop(0) is O(n) and silently turns your BFS quadratic.

• Snapshot len(q) to batch a level. Increment the level counter only after the whole batch drains.

• Ordinary BFS certifies fewest edges. Equal positive edge cost turns that into minimum cost; unequal weights require a weight-appropriate method, not automatically Dijkstra when negative edges exist.

Corrective source notes

• CPython 3.14.0 collections documentation — deque end-operation and list front-pop costs; read fresh 2026-10-09.
• Breadth First Search - Algorithms for Competitive Programming — BFS discovers shortest paths by number of edges in an unweighted graph. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.