BFS in Depth
Why this exists
You want the fewest moves: the fewest letter changes from hit to cog, the fewest wheel turns to open a lock, the fewest hops between two routers, the shortest walk through a maze. If every move costs the same, there is an algorithm that answers this in time proportional to the size of the graph, with no priority queue, no relaxation rounds and no cleverness: explore everything one move away, then everything two moves away, and so on. That is breadth-first search (BFS), and its defining guarantee — the first time it reaches a vertex is along a shortest path — is what makes it the workhorse of unweighted search.
BFS has been invented several times. Konrad Zuse described it in 1945 for finding connected components, in a thesis that was rejected and not published until 1972. Edward F. Moore published it in 1959 as an algorithm for the shortest path through a maze ("The shortest path through a maze", Proceedings of the International Symposium on the Theory of Switching). C. Y. Lee rediscovered it in 1961 for routing wires on circuit boards, where it is still called the Lee algorithm: flood the grid from the source with distance labels, then trace back from the target. Every one of those uses — components, mazes, wire routing — is in this lesson.
The Graphs overview showed BFS in twenty lines. This lesson proves why it works (the two-distances invariant), and then pushes it in every direction it can go: path reconstruction, many sources at once, grids, edges that cost 0 or 1 (0-1 BFS), searching from both ends (bidirectional BFS, with the stopping rule people get wrong), searching puzzle states that are never stored, bipartiteness and shortest cycles. You need the vocabulary and the state-modeling habits from Graph Modeling, and a queue from Queues & Deques.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "minimum number of steps / moves / operations / jumps", all steps equal | BFS from the start |
| "shortest path" in an unweighted graph or grid | BFS with distance labels |
| "print the path", "reconstruct the route" | BFS with a parent array, walk back from the target |
| "distance from every cell to the nearest X", "all fires spread at once", "rotting" | Multi-source BFS: enqueue every source at distance 0 |
| "minutes until everything is infected/filled" | Multi-source BFS; answer = largest distance |
| Edge costs are only 0 and 1 ("free moves" and "paid moves", "remove a wall costs 1") | 0-1 BFS with a deque |
| Single source and single target, huge branching factor, both ends known | Bidirectional BFS |
| Puzzle, lock, word transformation, "state of the board" | BFS over an implicit state graph |
| "can the vertices be split into two groups with no edge inside a group", "two teams" | BFS two-colouring (bipartite check) |
| "shortest cycle", "girth" | BFS from every vertex |
| "level by level", "nodes at distance k", "the k-th ring" | BFS processing one layer at a time |
| Weights are small integers (1..C) | Dial's algorithm (bucketed BFS), or split edges into unit edges if tiny |
The meta-trigger: minimize a count of uniform-cost moves. If moves have different non-negative costs, BFS is wrong and you need Dijkstra (unless the costs are only 0 and 1).
Intuition & first principles
Drop a stone in a pond. The ripple reaches every point at distance 1 before any point at distance 2, and every point at distance 2 before any at distance 3. BFS is the discrete version: from the source, label all neighbours with 1; from those, label all unlabelled neighbours with 2; and so on. A vertex gets the label exactly when it is first touched by the -th ripple.
Why would that label be the shortest distance? Because a vertex at true distance has a neighbour at true distance (the second-to-last vertex on a shortest path). If all vertices at distance are labelled correctly before anything at distance is processed, then when is processed it touches , and nothing touched earlier — anything that did would have been processed earlier and therefore be at distance less than , giving a path shorter than . That is the whole proof idea. The rest is making sure the processing order really is "by distance", and that is the job of the FIFO queue.
The queue is the mechanism that turns "ripples" into code. Vertices are labelled when they are discovered (enqueued) and expanded when they are dequeued. Since a vertex labelled enqueues only vertices labelled , and everything is first-in-first-out, the queue at any moment looks like : a block of distance- vertices followed by a block of distance- vertices. Two consecutive values, in order. That two-distances invariant is the precise statement behind the ripple picture, and it is what we prove below.
Contrast with DFS, which uses a stack: it plunges down one path as far as possible. DFS reaches every reachable vertex too, but the first path it finds to a vertex can be arbitrarily long. Same graph, same visited set; the order is everything.
Mechanics
The algorithm
BFS(G, s):
dist[v] = infinity for all v; parent[v] = none for all v
dist[s] = 0
queue = [s]
while queue not empty:
u = dequeue()
for each neighbour v of u:
if dist[v] == infinity: # first discovery
dist[v] = dist[u] + 1
parent[v] = u
enqueue(v)
Three details matter:
- Mark on discovery, not on dequeue. Setting
dist[v]when is enqueued guarantees each vertex enters the queue once. If you mark on dequeue instead, a vertex with many labelled neighbours is enqueued many times; distances stay correct but the queue can grow to and the running time degrades. - The test is "unlabelled", not "smaller distance". In BFS the first label is final. There is no relaxation.
parentrecords the edge that discovered each vertex. The parent edges form the BFS tree, a shortest-path tree rooted at .
The example graph
Eight vertices, ten undirected edges. Sources and layers:
flowchart LR
A["A (d=0)"] --- B["B (d=1)"]
A --- C["C (d=1)"]
B --- D["D (d=2)"]
C --- D
C --- E["E (d=2)"]
D --- F["F (d=3)"]
E --- F
E --- G["G (d=3)"]
F --- H["H (d=4)"]
G --- H
Trace: BFS from A
Adjacency lists are in alphabetical order. This table was produced by running the generator scripts/traces/bfs_graph.py (the same run the visualizer below plays back).
| Step | Dequeue (dist) | Neighbours scanned | Newly labelled | Queue after | Labels so far |
|---|---|---|---|---|---|
| 0 | — | — | A=0 | [A] | A0 |
| 1 | A (0) | B, C | B=1, C=1 | [B, C] | A0 B1 C1 |
| 2 | B (1) | A, D | D=2 | [C, D] | + D2 |
| 3 | C (1) | A, D, E | E=2 | [D, E] | + E2 |
| 4 | D (2) | B, C, F | F=3 | [E, F] | + F3 |
| 5 | E (2) | C, F, G | G=3 | [F, G] | + G3 |
| 6 | F (3) | D, E, H | H=4 | [G, H] | + H4 |
| 7 | G (3) | E, H | — | [H] | — |
| 8 | H (4) | F, G | — | [] | — |
Read the "Queue after" column against the invariant: [B, C] is all 1s, [C, D] is 1 then 2, [D, E] all 2s, [E, F] is 2 then 3, [F, G] all 3s, [G, H] is 3 then 4. Never more than two distinct values, always in non-decreasing order. The parent pointers are B←A, C←A, D←B, E←C, F←D, G←E, H←F, so the reconstructed path to H is A → B → D → F → H, length 4. (A → C → E → G → H is another shortest path; BFS returns whichever its neighbour order discovers first.)
Path reconstruction
parent gives a path backwards: from the target, follow parents to the source, then reverse. The cost is . If the target was never labelled, there is no path. Store parents as an array indexed by vertex for explicit graphs, or a hash map state → previous state for implicit graphs. To print all shortest paths (Word Ladder II), keep, for each vertex, the list of all parents at distance exactly one less; that list forms a DAG of shortest paths that you then enumerate with DFS.
Multi-source BFS
"Distance from each cell to the nearest gate", "minutes until every orange rots": the answer for a vertex is the distance to the nearest of several sources. Running one BFS per source costs . Instead, put all sources in the queue at distance 0 before the loop. This is exactly a single BFS from a virtual super-source joined by an edge to every real source, with that first layer hidden; the two-distances invariant and the proof go through unchanged, and the cost is one traversal, . The parent of a vertex then tells you which source it is closest to (follow parents to the root) — the basis of discrete Voronoi diagrams on grids.
BFS on grids
A grid is an implicit graph: cell (r, c) is a vertex, the open cells among its 4 (or 8) neighbours are its edges. Nothing changes in the algorithm; the bookkeeping lives in a 2D dist array and a direction table, as in Matrices & 2D Grids. The Lee algorithm is exactly this. Step through it on a small maze:
Two grid-specific habits pay off: flatten (r, c) to r * C + c so a deque of integers replaces a deque of tuples (a large constant-factor win in Python and Java), and mark walls as visited up front so the inner loop has one test instead of two.
0-1 BFS
Suppose edges cost either 0 or 1: following the arrow in a grid is free, changing it costs 1; walking on empty cells is free, breaking a wall costs 1. Plain BFS is wrong (it treats both as 1), and Dijkstra works but pays per operation for a heap. 0-1 BFS replaces the queue with a deque: when relaxing an edge of weight 0, push the vertex to the front; weight 1, push to the back. Pop from the front.
flowchart LR
F["front"] --> X1["d"] --> X2["d"] --> X3["d"] --> Y1["d+1"] --> Y2["d+1"] --> B["back"]
W0["relax with weight 0: label d, push front"] -.-> X1
W1["relax with weight 1: label d+1, push back"] -.-> Y2
The deque keeps the same two-distances shape as the BFS queue — a block of then a block of — so popping the front always yields a minimum-distance vertex, just like Dijkstra's heap would. Unlike plain BFS, a vertex's label can improve once (from to , if a 0-edge reaches it after a 1-edge did), so we use relaxation (if dist[u] + w < dist[v]) and skip stale deque entries. Each vertex is pushed at most twice, so the cost stays . The proof is in the correctness section.
Bidirectional BFS
When you know both the source and the target and the graph branches heavily, search from both ends and stop when the two searches meet. If every vertex has about neighbours and the answer is , a one-way BFS labels about vertices; two searches of depth label about . The numbers, computed by script:
| Branching | Depth | One-way BFS | Bidirectional | Ratio |
|---|---|---|---|---|
| 10 | 6 | 1,111,111 | 2,222 | ≈ 500× |
| 3 | 10 | 88,573 | 728 | ≈ 122× |
Real graphs do not branch uniformly, so measure. On the 8-puzzle (181,440 reachable states, average branching under 3, and many paths re-converge), from one of the two hardest positions (31 moves from solved, 867254301 with 0 as the blank), one-way BFS labels all 181,440 states before reaching the goal; layer-synchronous bidirectional BFS labels 20,220 states in total across both sides — about 9× fewer. Far from the theoretical ratio, because the puzzle's layers stop growing exponentially after depth 20 or so (the largest layers are at depths 22 and 24), but still a big win.
The stopping rule. The tempting rule — "alternate one vertex from each side; the moment a scanned neighbour has been seen by the other side, return the sum of the two distances" — is wrong. Here is a six-vertex counterexample found by a random search:
flowchart LR
S["S"] --- A["A"]
A --- Bv["B"]
Bv --- C["C"]
S --- D["D"]
D --- C
C --- T["T"]
With adjacency of C in the order B, D, T: pop S (label A and D at distance 1 from S); pop T (label C at distance 1 from T); pop A (label B at distance 2 from S); pop C, whose first neighbour B was seen from S — the naive rule returns , but S → D → C → T has length 3. The meeting through B was found first only because the S side had partially expanded a deeper layer.
The correct rule: expand whole layers, one side at a time (usually the side with the smaller frontier). While expanding a layer from side , check every scanned edge against the other side's labels; after the layer, if any meeting was seen, return the minimum of over those meetings. With complete layers on both sides, every meeting found in the first meeting layer has the same, optimal length (proved below), so taking the minimum is a safety habit that costs nothing. If one frontier empties without a meeting, is unreachable.
BFS over implicit state graphs
Puzzles are graphs whose vertices are configurations. The code is the same BFS with three substitutions: the start is a configuration, neighbours(state) generates legal moves, and dist is a hash map from state to distance (or an array if states encode to small integers).
- Word ladder. State = a word. Neighbours: for each position, each of the 25 other letters, keep the result if it is in the word set. With the example dictionary
hot, dot, dog, lot, log, cog, the ladderhit → hot → dot → dog → coghas 5 words (4 transformations); removecogfrom the list and there is none. - Open the lock. State = 4 digits, 8 neighbours each, dead-ends are deleted vertices. states. With dead-ends
0201, 0101, 0102, 1212, 2002, the target0202is 6 turns away; target0009with dead-end8888is 1 turn (turn the last wheel backwards). - Sliding puzzle (2×3). State = the 6 tiles as a string, neighbours = swap the blank with an adjacent tile. 360 states reachable; the farthest is 21 moves;
[[4,1,2],[5,0,3]]is 5 moves from solved, and[[1,2,3],[5,4,0]]is in the other parity class, so unreachable.
Estimate the state count before you run (see Graph Modeling): BFS has to store every visited state, so memory, not time, is usually what breaks first.
Bipartite check
A graph is bipartite if its vertices can be coloured with two colours so that every edge joins different colours. Run BFS and colour each vertex by the parity of its distance: colour[v] = dist[v] % 2. The graph is bipartite exactly when no edge joins two vertices of the same colour. Any edge inside one BFS layer (same distance, same colour) proves an odd cycle; every edge of a BFS goes between consecutive layers or within a layer (never across two layers, by the shortest-path property), so "no edge within a layer" is exactly "the parity colouring works". Run it from every uncoloured vertex to cover disconnected graphs.
Shortest cycle (girth)
In an undirected unweighted graph, run BFS from a root . When scanning finds a neighbour that is already labelled and is not 's parent, the tree paths and plus the edge form a closed walk of length , which contains a cycle no longer than that. The minimum of this value over all such edges, minimized again over every root , is the girth. One root is not enough: in random tests a BFS from a vertex far from the short cycle reported 6 when the girth was 3. Rooted at a vertex on a shortest cycle, the BFS finds it exactly. Cost: BFS runs, . For directed graphs, the shortest cycle through is , again minimized over all .
The ladder: brute force → better → optimal
Problem: shortest path (number of edges) from to every vertex of an unweighted graph with vertices and edges.
Rung 1: enumerate paths with DFS
Try every simple path from , record the shortest length per vertex. Correct, and exponential: a grid graph has a number of simple paths exponential in its side length. Useful only as a brute-force oracle for testing on graphs of 8–10 vertices.
Rung 2: Bellman-Ford with unit weights
Relax every edge times. . Correct because after rounds every vertex reachable in edges has its true distance. Wasteful: in each round, most relaxations change nothing.
Rung 3: Dijkstra with unit weights
with a binary heap. Correct. The heap is pure overhead: with unit weights, the order in which vertices are finalized is just "by layer", which a FIFO queue already provides.
Rung 4: BFS
, a queue instead of a heap, each vertex enqueued once, each edge scanned once (twice if undirected). Optimal: any algorithm must, in the worst case, look at every edge.
Rung 5 (single pair): bidirectional BFS
Same worst case, , but on graphs with large branching factor the explored region shrinks from about to vertices. Only helps for a single source–target pair, and needs the reverse graph if edges are directed.
| Rung | Method | Time | Extra space | Why it improves |
|---|---|---|---|---|
| 1 | DFS over all simple paths | exponential | Baseline oracle | |
| 2 | Bellman-Ford, unit weights | Polynomial: rounds bound the path length | ||
| 3 | Dijkstra, unit weights | Finalizes each vertex once | ||
| 4 | BFS | FIFO order already is distance order; no heap | ||
| 5 | Bidirectional BFS (one pair) | worst | Explores instead of |
And the weighted generalization of rung 4: edge weights in → 0-1 BFS, ; small integer weights → Dial's buckets, ; arbitrary non-negative → Dijkstra.
Correctness
Let be the true shortest-path distance (number of edges), if unreachable. The argument follows CLRS (4th ed., §20.2), compressed.
Lemma 1 (labels are never too small)
At all times, for every labelled , dist[v] .
Induction on enqueue operations. dist[s] = 0 = δ(s, s). When is labelled from , dist[v] = dist[u] + 1 ; the last step is the triangle inequality (a path to plus the edge is a path to ). Labels never change afterwards.
Lemma 2 (the two-distances invariant)
If the queue holds (front to back), then dist[v_1] dist[v_2] dist[v_r] dist[v_1] + 1.
Induction on queue operations. Initially the queue is [s]; trivially true. Dequeue : the new front is with dist[v_2] dist[v_1], so dist[v_r] dist[v_1] + 1 dist[v_2] + 1; order is untouched. Enqueue while expanding (which was just dequeued, so dist[u] dist[v_1] of the current front): dist[v] = dist[u] + 1 dist[v_1] + 1, which is the upper bound; and dist[v_r] dist[u] + 1 = dist[v] because before was dequeued, was the front and the invariant gave dist[v_r] dist[u] + 1. So the new last element is at least the old last and at most front + 1.
Corollary: vertices are dequeued in non-decreasing order of dist, and a vertex enqueued after another has a label at least as large.
Theorem (BFS computes shortest paths)
When BFS ends, dist[v] = δ(s, v) for every , and for reachable , the path to parent[v] followed by the edge to is a shortest path.
Suppose not, and let be a vertex with dist[v] and the smallest among such vertices. By Lemma 1, dist[v] , so is reachable and . Let be the vertex just before on a shortest path, so and, by minimality, dist[u] . Hence dist[v] dist[u] + 1. Consider the moment is dequeued and scans :
- If was unlabelled, it gets
dist[u] + 1. Contradiction. - If was already dequeued, then by the corollary
dist[v]dist[u]. Contradiction. - If was in the queue, then by Lemma 2
dist[v]dist[u] + 1. Contradiction.
So every label is exact. The parent claim follows: dist[v] = dist[parent[v]] + 1, and inducting along parents gives a path of exactly dist[v] edges.
0-1 BFS
Invariant: the deque's labels are non-decreasing from front to back and span at most two consecutive values , where is the front's label; every vertex already popped with a non-stale entry has its final distance. Popping the front gives a vertex of minimum label among all deque entries, exactly what Dijkstra's heap would give, so the Dijkstra correctness argument applies verbatim (all weights non-negative, a popped minimum cannot be improved later). Relaxing with weight 0 gives label (push front: the deque stays sorted); weight 1 gives (push back: stays sorted, still within ). A vertex's label can drop at most once — from to — because every later label offered is at least the current front's label, so each vertex enters the deque at most twice: .
Bidirectional BFS with whole layers
Suppose side has complete labels for all vertices within distance of , side for all within distance of , and no vertex is labelled by both. Then : on a shortest path of length , the vertex at distance from is at distance from , so it would be labelled by both sides. Now expand side 's layer . Every meeting edge found has and , giving a real path of length . Combined with the lower bound, every meeting found has length exactly . If no meeting is found, the precondition holds again with and the argument repeats. The naive counterexample breaks the precondition: side 's labels at depth 2 were incomplete when the meeting was declared.
Complexity
Time. Each vertex is enqueued and dequeued at most once (marking on discovery), . Each vertex's adjacency list is scanned once, when it is dequeued, so the total scanning is for directed graphs and for undirected — . Total ; restricted to the part reachable from if you do not loop over all vertices. With an adjacency matrix, scanning a row costs , so BFS becomes . On an grid: .
Space. dist/parent: . The queue holds at most two layers at once, so its peak size is bounded by the two largest consecutive layers — on a grid from a corner, about the length of an anti-diagonal, ; on a tree with branching it is the last layer, . Implicit-graph BFS stores every visited state, which is why memory is the usual limit for puzzle search.
Best/average/worst. BFS to a specific target can stop when the target is dequeued (or, slightly earlier, when it is discovered), so the best case is tiny. Worst case explores everything. There is no "average" in a meaningful sense without a graph distribution; for search problems, use the branching-factor estimate .
Constants and cache behaviour. The queue itself is cheap (a ring buffer or an array with a head index). The cost is in the random accesses to dist[v] for each scanned neighbour. On large graphs, those accesses miss the cache, which is why CSR layouts and vertex reordering speed BFS up several times, and why high-performance BFS implementations (for example the "direction-optimizing" BFS of Beamer, Asanović and Patterson, 2012) switch to scanning unvisited vertices bottom-up when the frontier becomes a large fraction of the graph. In Python, collections.deque is the right queue (list.pop(0) is ); in Java, ArrayDeque (not LinkedList); in JavaScript, an array plus a head index (shift() is in the worst case).
Implementation
BFS with distances, parents and path reconstruction
The example graph above with A..H as 0..7, plus an isolated vertex 8 to test unreachability. Same assertions in every language.
from collections import deque
def bfs(adj, s):
n = len(adj)
dist = [-1] * n
parent = [-1] * n
dist[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1: # first discovery is final
dist[v] = dist[u] + 1
parent[v] = u
q.append(v)
return dist, parent
def path_to(parent, dist, t):
if dist[t] == -1:
return []
path = []
while t != -1:
path.append(t)
t = parent[t]
return path[::-1]
def build(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
return adj
if __name__ == "__main__":
# A..H = 0..7, vertex 8 isolated
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5), (4, 6), (5, 7), (6, 7)]
adj = build(9, edges)
dist, parent = bfs(adj, 0)
assert dist == [0, 1, 1, 2, 2, 3, 3, 4, -1]
assert path_to(parent, dist, 7) == [0, 1, 3, 5, 7] # A B D F H
assert path_to(parent, dist, 6) == [0, 2, 4, 6] # A C E G
assert path_to(parent, dist, 8) == []
assert path_to(parent, dist, 0) == [0]
print("bfs OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Bfs {
static int[][] bfs(List<List<Integer>> adj, int s) {
int n = adj.size();
int[] dist = new int[n], parent = new int[n];
Arrays.fill(dist, -1);
Arrays.fill(parent, -1);
dist[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.add(v);
}
}
}
return new int[][] {dist, parent};
}
static List<Integer> pathTo(int[] parent, int[] dist, int t) {
List<Integer> path = new ArrayList<>();
if (dist[t] == -1) return path;
for (int v = t; v != -1; v = parent[v]) path.add(v);
Collections.reverse(path);
return path;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int n = 9;
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {4, 6}, {5, 7}, {6, 7}};
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[][] r = bfs(adj, 0);
int[] dist = r[0], parent = r[1];
check(Arrays.equals(dist, new int[] {0, 1, 1, 2, 2, 3, 3, 4, -1}), "dist");
check(pathTo(parent, dist, 7).equals(List.of(0, 1, 3, 5, 7)), "path to H");
check(pathTo(parent, dist, 6).equals(List.of(0, 2, 4, 6)), "path to G");
check(pathTo(parent, dist, 8).isEmpty(), "unreachable");
check(pathTo(parent, dist, 0).equals(List.of(0)), "source");
System.out.println("bfs OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
std::pair<std::vector<int>, std::vector<int>> bfs(const std::vector<std::vector<int>>& adj, int s) {
int n = static_cast<int>(adj.size());
std::vector<int> dist(n, -1), parent(n, -1);
dist[s] = 0;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
return {dist, parent};
}
std::vector<int> pathTo(const std::vector<int>& parent, const std::vector<int>& dist, int t) {
std::vector<int> path;
if (dist[t] == -1) return path;
for (int v = t; v != -1; v = parent[v]) path.push_back(v);
std::reverse(path.begin(), path.end());
return path;
}
int main() {
int n = 9;
std::vector<std::pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4},
{3, 5}, {4, 5}, {4, 6}, {5, 7}, {6, 7}};
std::vector<std::vector<int>> adj(n);
for (auto [u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
auto [dist, parent] = bfs(adj, 0);
assert((dist == std::vector<int>{0, 1, 1, 2, 2, 3, 3, 4, -1}));
assert((pathTo(parent, dist, 7) == std::vector<int>{0, 1, 3, 5, 7}));
assert((pathTo(parent, dist, 6) == std::vector<int>{0, 2, 4, 6}));
assert(pathTo(parent, dist, 8).empty());
assert((pathTo(parent, dist, 0) == std::vector<int>{0}));
std::cout << "bfs OK\n";
}
function bfs(adj: number[][], s: number): { dist: number[]; parent: number[] } {
const n = adj.length;
const dist = new Array<number>(n).fill(-1);
const parent = new Array<number>(n).fill(-1);
dist[s] = 0;
const q: number[] = [s];
let head = 0; // array + head index: O(1) dequeue, unlike shift()
while (head < q.length) {
const u = q[head++];
for (const v of adj[u]) {
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
return { dist, parent };
}
function pathTo(parent: number[], dist: number[], t: number): number[] {
if (dist[t] === -1) return [];
const path: number[] = [];
for (let v = t; v !== -1; v = parent[v]) path.push(v);
return path.reverse();
}
function check(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 5], [4, 6], [5, 7], [6, 7]];
const adj: number[][] = Array.from({ length: 9 }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const { dist, parent } = bfs(adj, 0);
check(dist.join() === "0,1,1,2,2,3,3,4,-1", "dist");
check(pathTo(parent, dist, 7).join() === "0,1,3,5,7", "path to H");
check(pathTo(parent, dist, 6).join() === "0,2,4,6", "path to G");
check(pathTo(parent, dist, 8).length === 0, "unreachable");
check(pathTo(parent, dist, 0).join() === "0", "source");
console.log("bfs OK");
0-1 BFS on a grid of arrows
Each cell holds an arrow (1 right, 2 left, 3 down, 4 up). Moving in the arrow's direction costs 0; any other direction costs 1 (you "repaint" the arrow). Find the minimum cost from the top-left to the bottom-right cell. This is LeetCode 1368; the test grids are its published examples.
from collections import deque
DIRS = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
def min_cost(grid):
R, C = len(grid), len(grid[0])
INF = float("inf")
dist = [[INF] * C for _ in range(R)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
d = dist[r][c]
for sign, (dr, dc) in DIRS.items():
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C):
continue
w = 0 if grid[r][c] == sign else 1
if d + w < dist[nr][nc]:
dist[nr][nc] = d + w
if w == 0:
dq.appendleft((nr, nc)) # same distance: front
else:
dq.append((nr, nc)) # distance + 1: back
return dist[R - 1][C - 1]
if __name__ == "__main__":
assert min_cost([[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]) == 3
assert min_cost([[1, 1, 3], [3, 2, 2], [1, 1, 4]]) == 0
assert min_cost([[1, 2], [4, 3]]) == 1
assert min_cost([[4]]) == 0
print("0-1 bfs OK")
import java.util.ArrayDeque;
import java.util.Arrays;
public class ZeroOneBfs {
static final int[][] DIRS = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // index = sign
static int minCost(int[][] grid) {
int R = grid.length, C = grid[0].length;
int[][] dist = new int[R][C];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[0][0] = 0;
ArrayDeque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] {0, 0});
while (!dq.isEmpty()) {
int[] cur = dq.pollFirst();
int r = cur[0], c = cur[1], d = dist[r][c];
for (int sign = 1; sign <= 4; sign++) {
int nr = r + DIRS[sign][0], nc = c + DIRS[sign][1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int w = grid[r][c] == sign ? 0 : 1;
if (d + w < dist[nr][nc]) {
dist[nr][nc] = d + w;
if (w == 0) dq.addFirst(new int[] {nr, nc});
else dq.addLast(new int[] {nr, nc});
}
}
}
return dist[R - 1][C - 1];
}
static void check(boolean ok) { if (!ok) throw new AssertionError(); }
public static void main(String[] args) {
check(minCost(new int[][] {{1, 1, 1, 1}, {2, 2, 2, 2}, {1, 1, 1, 1}, {2, 2, 2, 2}}) == 3);
check(minCost(new int[][] {{1, 1, 3}, {3, 2, 2}, {1, 1, 4}}) == 0);
check(minCost(new int[][] {{1, 2}, {4, 3}}) == 1);
check(minCost(new int[][] {{4}}) == 0);
System.out.println("0-1 bfs OK");
}
}
#include <cassert>
#include <climits>
#include <deque>
#include <iostream>
#include <utility>
#include <vector>
int minCost(const std::vector<std::vector<int>>& grid) {
const int DR[5] = {0, 0, 0, 1, -1}, DC[5] = {0, 1, -1, 0, 0}; // index = sign
int R = static_cast<int>(grid.size()), C = static_cast<int>(grid[0].size());
std::vector<std::vector<int>> dist(R, std::vector<int>(C, INT_MAX));
dist[0][0] = 0;
std::deque<std::pair<int, int>> dq;
dq.emplace_back(0, 0);
while (!dq.empty()) {
auto [r, c] = dq.front();
dq.pop_front();
int d = dist[r][c];
for (int sign = 1; sign <= 4; ++sign) {
int nr = r + DR[sign], nc = c + DC[sign];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
int w = grid[r][c] == sign ? 0 : 1;
if (d + w < dist[nr][nc]) {
dist[nr][nc] = d + w;
if (w == 0) dq.emplace_front(nr, nc);
else dq.emplace_back(nr, nc);
}
}
}
return dist[R - 1][C - 1];
}
int main() {
assert(minCost({{1, 1, 1, 1}, {2, 2, 2, 2}, {1, 1, 1, 1}, {2, 2, 2, 2}}) == 3);
assert(minCost({{1, 1, 3}, {3, 2, 2}, {1, 1, 4}}) == 0);
assert(minCost({{1, 2}, {4, 3}}) == 1);
assert(minCost({{4}}) == 0);
std::cout << "0-1 bfs OK\n";
}
const DR = [0, 0, 0, 1, -1];
const DC = [0, 1, -1, 0, 0]; // index = sign
function minCost(grid: number[][]): number {
const R = grid.length;
const C = grid[0].length;
const dist = Array.from({ length: R }, () => new Array<number>(C).fill(Infinity));
dist[0][0] = 0;
// A deque as a ring buffer would be ideal; two stacks emulate push-front cheaply.
let front: number[] = [0];
let back: number[] = [];
let backHead = 0;
while (front.length > 0 || backHead < back.length) {
let cell: number;
if (front.length > 0) cell = front.pop()!;
else {
cell = back[backHead++];
}
const r = Math.floor(cell / C);
const c = cell % C;
const d = dist[r][c];
for (let sign = 1; sign <= 4; sign++) {
const nr = r + DR[sign];
const nc = c + DC[sign];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const w = grid[r][c] === sign ? 0 : 1;
if (d + w < dist[nr][nc]) {
dist[nr][nc] = d + w;
if (w === 0) front.push(nr * C + nc);
else back.push(nr * C + nc);
}
}
if (front.length === 0 && backHead > 1024 && backHead * 2 > back.length) {
back = back.slice(backHead);
backHead = 0;
}
}
return dist[R - 1][C - 1];
}
function check(ok: boolean): void {
if (!ok) throw new Error("assertion failed");
}
check(minCost([[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]) === 3);
check(minCost([[1, 1, 3], [3, 2, 2], [1, 1, 4]]) === 0);
check(minCost([[1, 2], [4, 3]]) === 1);
check(minCost([[4]]) === 0);
console.log("0-1 bfs OK");
A note on the TypeScript version: JavaScript has no built-in deque. The front stack holds weight-0 pushes (all at the current front distance , so their internal order does not matter) and the back queue holds weight-1 pushes. Popping the stack first and then the queue reproduces the deque order, because the stack only ever contains distance- entries while the queue contains distance- entries (pushed earlier as from layer ) followed by distance- ones. The stale-entry check is implicit: a popped cell whose dist already improved simply re-relaxes with the improved value, which is harmless.
Variant: multi-source BFS (rotting oranges)
All rotten oranges (2) are sources at minute 0; fresh oranges (1) rot one minute after a neighbour does. Answer: minutes until none are fresh, or -1.
from collections import deque
def oranges_rotting(grid):
R, C = len(grid), len(grid[0])
g = [row[:] for row in grid]
q = deque()
fresh = 0
for r in range(R):
for c in range(C):
if g[r][c] == 2:
q.append((r, c)) # every source at distance 0
elif g[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)): # one whole layer = one minute
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1:
g[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert oranges_rotting([[0, 2]]) == 0
assert oranges_rotting([[2, 1, 0, 1, 2]]) == 1 # each fresh orange sits next to a different source
print("multi-source OK")
Variant: bidirectional BFS, and the counterexample
naive_bidirectional implements the tempting node-alternating rule; bidirectional expands whole layers of the smaller side. The test graph is the six-vertex counterexample from the mechanics section (S, A, B, C, D, T = 0..5).
from collections import deque
def naive_bidirectional(adj, s, t):
"""WRONG: alternates single vertices and stops at the first meeting."""
if s == t:
return 0
ds, dt = {s: 0}, {t: 0}
qs, qt = deque([s]), deque([t])
while qs and qt:
for q, mine, other in ((qs, ds, dt), (qt, dt, ds)):
u = q.popleft()
for v in adj[u]:
if v in other:
return mine[u] + 1 + other[v]
if v not in mine:
mine[v] = mine[u] + 1
q.append(v)
if not q:
return -1
return -1
def bidirectional(adj, s, t):
"""Correct: expand one whole layer at a time, smaller frontier first."""
if s == t:
return 0
ds, dt = {s: 0}, {t: 0}
fs, ft = [s], [t]
while fs and ft:
if len(fs) > len(ft):
fs, ft, ds, dt = ft, fs, dt, ds
best = None
nxt = []
for u in fs:
for v in adj[u]:
if v in dt:
cand = ds[u] + 1 + dt[v]
best = cand if best is None else min(best, cand)
if v not in ds:
ds[v] = ds[u] + 1
nxt.append(v)
if best is not None:
return best
fs = nxt
return -1
def bfs_dist(adj, s, t):
dist = {s: 0}
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return dist.get(t, -1)
S, A, B, C, D, T = range(6)
adj = {S: [A, D], A: [S, B], B: [A, C], C: [B, D, T], D: [S, C], T: [C]}
assert bfs_dist(adj, S, T) == 3
assert naive_bidirectional(adj, S, T) == 4 # overshoots
assert bidirectional(adj, S, T) == 3
import random
random.seed(7)
for _ in range(2000):
n = random.randint(2, 10)
g = {i: [] for i in range(n)}
for i in range(n):
for j in range(i + 1, n):
if random.random() < 0.3:
g[i].append(j)
g[j].append(i)
assert bidirectional(g, 0, n - 1) == bfs_dist(g, 0, n - 1)
print("bidirectional OK")
Variant: word ladder, bipartite check and girth
Three more BFS applications in one runnable block.
from collections import deque
from string import ascii_lowercase
def ladder_length(begin, end, words):
word_set = set(words)
if end not in word_set:
return 0
dist = {begin: 1} # counts words, not moves
q = deque([begin])
while q:
w = q.popleft()
if w == end:
return dist[w]
for i in range(len(w)):
for ch in ascii_lowercase:
nw = w[:i] + ch + w[i + 1:]
if nw in word_set and nw not in dist:
dist[nw] = dist[w] + 1
q.append(nw)
return 0
def is_bipartite(adj):
n = len(adj)
colour = [-1] * n
for s in range(n):
if colour[s] != -1:
continue
colour[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if colour[v] == -1:
colour[v] = colour[u] ^ 1
q.append(v)
elif colour[v] == colour[u]:
return False # edge inside a layer: odd cycle
return True
def girth(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
best = float("inf")
for r in range(n): # one root is not enough
dist = [-1] * n
parent = [-1] * n
dist[r] = 0
q = deque([r])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
parent[v] = u
q.append(v)
elif parent[u] != v:
best = min(best, dist[u] + dist[v] + 1)
return -1 if best == float("inf") else best
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0
assert is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) # 4-cycle
assert not is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) # has triangles
assert is_bipartite([[], [2], [1]]) # disconnected
assert girth(7, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 6), (6, 3)]) == 3
assert girth(4, [(0, 1), (0, 2)]) == -1
assert girth(6, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]) == 6
print("applications OK")
Real-world uses
- Network routing and discovery. Hop-count routing (the RIP protocol's metric is hop count) and the flooding used by link-state protocols to distribute topology are BFS-shaped; the routers then run Dijkstra on the result. See the network layer page. Gossip protocols spread information in rounds that behave like a randomized BFS, which is why they reach nodes in rounds.
- Garbage collection. Cheney's copying collector (1970) is a BFS over the object graph that uses the to-space itself as the queue: a "scan" pointer chases a "free" pointer, with no extra memory at all. See memory allocators.
- Web crawlers. Crawling outward from seed URLs in BFS order finds high-quality pages early; a classic study by Najork and Wiener (2001) found that breadth-first crawling discovers high-PageRank pages early. Production crawlers use prioritized frontiers but keep the layered structure. See search engineering.
- Social networks. "Degrees of separation", "people you may know" (friends of friends = BFS layer 2), and LinkedIn-style connection degrees are BFS layers; with both endpoints known and branching factors in the hundreds, they are a natural fit for bidirectional search.
- VLSI and PCB routing. The Lee algorithm and its descendants route wires on grids; 0-1 BFS-style costs (vias cost more than straight segments) are common extensions.
- Graph databases and analytics. Shortest-path and k-hop neighbourhood queries in graph databases are BFS; the Graph500 benchmark ranks supercomputers by how fast they run BFS on huge synthetic graphs, measured in traversed edges per second.
- Puzzle solving and planning. Exhaustive state-space search settles questions like "God's number": the proof that every Rubik's cube position is solvable in at most 20 face turns (Rokicki, Kociemba, Davidson, Dethridge, 2010) combined symmetry reduction with a search over billions of cosets. Smaller puzzles (the 8-puzzle, Open the Lock) are solved by plain BFS in milliseconds.
- Package managers and build tools. Computing the transitive install set of a package, or everything affected by a changed file, is a reachability traversal over the dependency graph; BFS order also gives "how far away" each dependency is, which some tools use for conflict resolution and reporting.
Pitfalls & edge cases
- Marking visited on dequeue. Correct distances, but duplicate queue entries: on dense graphs the queue grows to and the time to dequeues with redundant scans. Mark when you enqueue.
- Using a list as a queue.
list.pop(0)in Python andArray.prototype.shiftin JavaScript can be ; a 10⁶-vertex BFS becomes quadratic. Usedeque,ArrayDeque, or an array with a head index. - Forgetting the source. Set
dist[s] = 0and mark it visited before the loop, or a neighbour re-enqueues it at distance 2. - Source equals target. Return 0 immediately (Word Ladder returns 1 because it counts words). Check the problem's convention.
- Off-by-one in "layers". "Minutes until all rot" is the number of layers after the sources, not the number of layers. The level-by-level loop (
for _ in range(len(q))) makes this explicit; when the grid has no fresh oranges the answer is 0, not 1. - Weighted edges. BFS on weighted graphs returns the fewest edges, not the cheapest path. If weights are 0/1 use 0-1 BFS; otherwise Dijkstra.
- 0-1 BFS without relaxation. Treating 0-1 BFS like plain BFS (mark on first discovery, never improve) gives wrong answers: a vertex first reached by a weight-1 edge may later be reached at the same front distance by a weight-0 edge.
- Bidirectional stopping. Node-alternating with an early return overshoots (counterexample above). Expand whole layers. For directed graphs, the backward search must use reversed edges.
- Bipartite check on disconnected graphs. Start a BFS from every uncoloured vertex.
- Girth from one root. Overestimates when the root is far from the shortest cycle; loop over all roots. In multigraphs, parallel edges form 2-cycles that the
parent[u] != vtest misses; handle them separately. - Grid bounds and walls. Check bounds before indexing; in Python negative indices silently wrap around to the other side of the grid.
- State encoding. In implicit graphs, a mutable state (a list) cannot be hashed; use tuples, strings, or packed integers. Copying the board for every neighbour can dominate the run time; encode compactly.
- Recursion is not an issue — BFS is naturally iterative. The memory of the queue and the visited set is the limit.
Variations
- Level-synchronous BFS. Process one whole layer per outer iteration (
for _ in range(len(q))). Gives layer numbers for free and is the basis of parallel BFS. - Multi-source BFS. Several sources at distance 0; equivalent to a super-source.
- 0-1 BFS. Deque, weights in .
- Dial's algorithm. Weights in : an array of buckets used circularly; where is the maximum distance. Between 0-1 BFS and Dijkstra.
- Bidirectional BFS. Two frontiers, whole-layer expansion, smaller side first.
- Direction-optimizing BFS. Switch between top-down (scan the frontier's edges) and bottom-up (each unvisited vertex looks for a parent in the frontier) depending on frontier size; large speedups on low-diameter graphs.
- BFS on implicit graphs. Neighbour generators instead of adjacency lists; hash sets for visited.
- Lexicographic BFS (LexBFS). A refinement that breaks ties between vertices by their neighbourhoods; it recognizes chordal graphs in linear time. A specialist tool.
- A* search. BFS/Dijkstra guided by a heuristic estimate of remaining distance; with a zero heuristic it is Dijkstra, and on unit weights Dijkstra is BFS. See shortest paths.
- Iterative deepening DFS. Same layer-by-layer guarantee with memory instead of , paid for with repeated work; covered in DFS in depth.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Message Route (CSES 1667) — Shortest route between two computers in an unweighted network, print the route. Teaches parents and path reconstruction.
Hint
BFS from computer 1 with a parent array; if computer is unlabelled print "IMPOSSIBLE", otherwise walk back and reverse.
2. Shortest Path in Binary Matrix (LeetCode 1091) — Fewest cells on a path through open cells with 8-directional moves. Teaches grid BFS with 8 neighbours and counting cells rather than moves.
Hint
Check the start and end cells are open. Distance of the start is 1 (cells counted). Eight direction pairs.
3. Labyrinth (CSES 1193) — Shortest path in a character grid, print the moves as L R U D. Teaches storing the move direction as the parent.
Hint
Store, for each cell, the direction used to enter it. Walk back from the end by undoing directions, then reverse the string.
4. Rotting Oranges (LeetCode 994) — All rotten fruit spreads at once. Teaches multi-source BFS and layer counting.
Hint
All rotten cells start in the queue. Count fresh cells; process layer by layer; stop when nothing fresh remains. The variant code above is a full solution.
5. 01 Matrix (LeetCode 542) — Distance from every cell to the nearest 0. Teaches reversing the question: BFS from all zeros at once instead of from every one.
Hint
Enqueue every 0 at distance 0, every 1 starts unlabelled. One multi-source BFS gives all answers in .
6. Is Graph Bipartite? (LeetCode 785) — Can the vertices be split into two sides with all edges crossing. Teaches parity colouring and disconnected inputs.
Hint
BFS two-colouring from each uncoloured vertex; an edge between equal colours means no.
Solution
from collections import deque
def is_bipartite(graph):
colour = [-1] * len(graph)
for s in range(len(graph)):
if colour[s] != -1:
continue
colour[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in graph[u]:
if colour[v] == -1:
colour[v] = 1 - colour[u]
q.append(v)
elif colour[v] == colour[u]:
return False
return True
assert is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]) is True
assert is_bipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) is False
time, space.
7. Building Teams (CSES 1668) — Split pupils into two teams so that no two friends share a team, print an assignment. Teaches the same check with output, at scale.
Hint
Same as above; print colour + 1. Use iterative BFS and fast input.
8. Open the Lock (LeetCode 752) — Fewest wheel turns avoiding dead-end combinations. Teaches BFS over an implicit graph of states.
Hint
Neighbours: 8 per state. Dead-ends are pre-marked visited; check the start is not one. The Graph Modeling lesson has a full implementation.
9. Word Ladder (LeetCode 127) — Fewest words in a one-letter-at-a-time transformation. Teaches neighbour generation cost and bidirectional search.
Hint
Generate candidates per word and test set membership. For speed, run layer-synchronous bidirectional BFS and always expand the smaller frontier.
10. Sliding Puzzle (LeetCode 773) — Fewest moves to solve a 2×3 sliding puzzle. Teaches encoding boards as strings and parity classes.
Hint
State = 6-character string. Precompute, for each blank position 0..5, the positions it can swap with. At most 360 states are reachable.
Solution
from collections import deque
def sliding_puzzle(board):
start = "".join(str(x) for row in board for x in row)
goal = "123450"
swaps = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
dist = {start: 0}
q = deque([start])
while q:
s = q.popleft()
if s == goal:
return dist[s]
z = s.index("0")
for j in swaps[z]:
t = list(s)
t[z], t[j] = t[j], t[z]
t = "".join(t)
if t not in dist:
dist[t] = dist[s] + 1
q.append(t)
return -1
assert sliding_puzzle([[1, 2, 3], [4, 0, 5]]) == 1
assert sliding_puzzle([[1, 2, 3], [5, 4, 0]]) == -1
assert sliding_puzzle([[4, 1, 2], [5, 0, 3]]) == 5
At most 360 reachable states with at most 3 moves each; effectively constant.
11. Minimum Obstacle Removal to Reach Corner (LeetCode 2290) — Fewest walls to remove to cross a grid. Teaches 0-1 BFS: entering an empty cell costs 0, a wall costs 1.
Hint
The cost of a move is the value of the cell you enter. Deque: push front for 0, back for 1.
Solution
from collections import deque
def minimum_obstacles(grid):
R, C = len(grid), len(grid[0])
INF = float("inf")
dist = [[INF] * C for _ in range(R)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
w = grid[nr][nc]
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
(dq.append if w else dq.appendleft)((nr, nc))
return dist[R - 1][C - 1]
assert minimum_obstacles([[0, 1, 1], [1, 1, 0], [1, 1, 0]]) == 2
assert minimum_obstacles([[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0]]) == 0
time and space.
12. Shortest Cycle in a Graph (LeetCode 2608) — Length of the shortest cycle in an undirected graph, . Teaches BFS from every vertex and why one root is not enough.
Hint
From each root, any labelled non-parent neighbour gives a candidate . Take the minimum over all roots. fits the limits.
Solution
from collections import deque
def find_shortest_cycle(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
best = float("inf")
for r in range(n):
dist = [-1] * n
par = [-1] * n
dist[r] = 0
q = deque([r])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
par[v] = u
q.append(v)
elif par[u] != v:
best = min(best, dist[u] + dist[v] + 1)
return -1 if best == float("inf") else best
assert find_shortest_cycle(7, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 6], [6, 3]]) == 3
assert find_shortest_cycle(4, [[0, 1], [0, 2]]) == -1
time, space.
13. Labyrinth (Codeforces 1063B) — Count cells reachable with at most left moves and right moves (up and down are free). Teaches choosing the right cost: minimize left moves with 0-1 BFS, and the right moves follow.
Hint
For a cell at column offset from the start, right moves = left moves + . So minimizing left moves minimizes both. 0-1 BFS where a left move costs 1 and everything else costs 0.
14. Word Ladder II (LeetCode 126) — Print every shortest transformation sequence. Teaches building the shortest-path DAG (all parents one layer up) and enumerating it, with a careful eye on memory.
Hint
BFS layer by layer; for each newly reached word record every parent from the current layer; remove a whole layer from the word set only after the layer is finished. Then DFS backwards from the end word over the parent lists.
Common mistakes & interview follow-ups
"Prove BFS gives shortest paths." State the two-distances invariant (queue labels non-decreasing, spanning at most and ), then the minimal-counterexample argument: the first wrongly labelled vertex on a shortest path would have been labelled correctly by its predecessor.
"What if edges have weights?" 0 and 1: 0-1 BFS. Small integers: Dial's buckets or splitting edges into unit edges. General non-negative: Dijkstra. Negative: Bellman-Ford.
"What if the graph does not fit in memory?" For implicit graphs, iterative deepening DFS (no visited set, memory) or frontier search that keeps only the last two layers. For huge explicit graphs, external-memory or distributed level-synchronous BFS processes one layer at a time.
"How do you speed it up for a single pair?" Bidirectional BFS, expanding the smaller frontier and full layers; quote the argument and the stopping rule. With a good heuristic, A*.
"What is the space complexity?" for labels, plus the queue's peak — two layers. On a complete -ary search tree that is , which is the reason IDDFS exists.
"Can you return all shortest paths?" Keep all parents one layer up; the shortest-path DAG can have exponentially many paths, so warn about output size.
"Why not DFS for shortest paths?" DFS finds a path, not the shortest, and making it find the shortest requires exploring all paths. Give a 3-vertex example: a triangle explored A → B → C labels C at depth 2 although A–C is an edge.
Mistakes interviewers watch for: marking on dequeue; list.pop(0); forgetting multiple components; returning the layer count off by one; using BFS on weighted graphs; a bidirectional search that stops at the first touch while layers are partial.
Quick quiz
1. In the trace above, the queue after dequeuing E is [F, G]. What are their labels, and why can the queue never contain labels 2 and 4 at the same time?
Answer
F = 3, G = 3. By the two-distances invariant, all labels in the queue lie in where is the front's label; a 4 is only enqueued while expanding a 3, at which point every 2 has already been dequeued.
2. A grid has 500,000 open cells and 5 exits. You need the distance from every cell to its nearest exit. How many BFS runs?
Answer
One: a multi-source BFS with all 5 exits in the queue at distance 0. Five separate runs plus a minimum gives the same answer at 5× the cost.
3. Why does 0-1 BFS push weight-0 neighbours to the front?
Answer
Their label equals the current front label ; pushing to the front keeps the deque sorted ('s before 's), so the next pop is still a minimum-distance vertex, as Dijkstra requires.
4. Branching factor 10, answer at depth 6. Roughly how many vertices does one-way BFS label, and how many does bidirectional BFS label?
Answer
One-way: . Bidirectional (depth 3 each side): , about 500× fewer.
5. You BFS-colour a connected graph and find an edge between two vertices both at distance 3 from the root. What can you conclude?
Answer
The graph is not bipartite: the two tree paths to the root plus that edge form a closed walk of odd length , which contains an odd cycle.
Further reading / sources
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., §20.2 "Breadth-first search" (the lemmas and theorem above follow its structure).
- Edward F. Moore, "The shortest path through a maze", Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959.
- C. Y. Lee, "An algorithm for path connections and its applications", IRE Transactions on Electronic Computers EC-10(3), 1961.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., §4.1 (BreadthFirstPaths) and §4.2.
- Steven S. Skiena, The Algorithm Design Manual, 3rd ed., §7.6 "Breadth-First Search" and §7.7 "Applications of BFS".
- cp-algorithms: Breadth-first search and 0-1 BFS.
- Ira Pohl, "Bi-directional search", Machine Intelligence 6, 1971 — the original analysis of bidirectional search.
- Scott Beamer, Krste Asanović, David Patterson, "Direction-optimizing breadth-first search", SC 2012.
- C. J. Cheney, "A nonrecursive list compacting algorithm", Communications of the ACM 13(11), 1970 (BFS-based copying garbage collection).
- Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge, "The diameter of the Rubik's Cube group is twenty", SIAM Journal on Discrete Mathematics 27(2), 2013 (conference announcement 2010).
Previous lesson: Graph Modeling & Implicit Graphs · Next lesson: DFS in Depth
Related: Graphs overview · Queues, Deques & Circular Buffers · Matrices & 2D Grids · Shortest Paths · Topological Sort · Bipartite Matching · Course home