-
Notifications
You must be signed in to change notification settings - Fork 0
019 — BFS
DFS goes deep first, backing out only when a branch dead-ends. BFS makes the opposite trade: explore wide before deep, visiting everything one step away before anything two steps away. That single ordering change is what makes BFS the go-to pattern whenever "step" has a real-world cost and you need the fewest of them.
The Queues and Deques chapter covered the data structure itself — FIFO ordering, where the first thing added is the first thing removed. This chapter is about recognizing when that ordering is exactly what a traversal needs: BFS's queue: [Int] array is what guarantees everything at the current distance gets processed before anything one step farther.
Picture dropping a pebble into a still pond. The ripple doesn't jump straight to the far shore — it expands outward as a perfect ring, reaching every point at distance 1 from the drop before touching anything at distance 2, and everything at distance 2 before distance 3. If you wanted to know the shortest distance from the drop point to a specific lily pad, you wouldn't need to trace any particular path — you'd just note which ripple was the first to reach it. That's the guarantee: the ripple that first touches a point traveled the shortest possible distance to get there, because every closer point was necessarily touched by an earlier, smaller ripple first.
BFS is that ripple, implemented with a queue: process everything at the current distance before letting anything at the next distance in.
BFS is a strong reach when you see:
- "Shortest path" / "minimum number of steps" / "fewest moves" in an unweighted graph or grid — "shortest path in a binary matrix," "minimum number of knight moves," "word ladder" (each word transformation is one equal-cost step). BFS finds shortest paths in unweighted graphs the same way Dijkstra does in weighted ones, but without needing a priority queue.
- "Level order" traversal of a tree, or anything asking for per-level results — "binary tree level order traversal," "average of levels in a binary tree," "minimum depth of a binary tree" — the queue naturally groups nodes by distance-from-root, i.e. by level.
- "Nearest" combined with multiple starting points at once — "rotting oranges" (multiple rotten oranges spread simultaneously), "walls and gates" (multiple gates, find distance to nearest one) — BFS starting from all sources at once, pushed into the queue together, still guarantees each cell is reached via its shortest path from whichever source is closest.
- Grid/maze problems explicitly needing the minimum number of moves, not just any valid path — if any-valid-path were enough, DFS would do; the word "minimum" or "shortest" is what tips it to BFS.
The unifying tell: unweighted "distance" matters — every edge/move costs exactly 1, and you need the fewest of them, not just any sequence that works.
BFS spreading outward from node A — the frontier (queue contents) expands one full ring at a time:
A
/ \
B C
/ / \
D E F
\
G
queue: [A] visited: {A}
→ dequeue A, enqueue B, C
queue: [B, C] visited: {A,B,C} ← distance-1 ring, all in queue together
→ dequeue B, enqueue D
→ dequeue C, enqueue E, F
queue: [D, E, F] visited: {A,B,C,D,E,F} ← distance-2 ring
→ dequeue D (no children)
→ dequeue E (no children)
→ dequeue F, enqueue G
queue: [G] visited: {A,B,C,D,E,F,G} ← distance-3 ring
G is reached only after EVERY distance-2 node has been fully
processed — that's what guarantees G's distance (3) is minimal.
func bfsTemplate(startingAt start: Int, neighbors: (Int) -> [Int]) -> [Int: Int] {
var distance: [Int: Int] = [start: 0] // 🔧 Fill in: whatever per-node info you need to track.
var queue: [Int] = [start]
var head = 0 // index-based dequeue avoids O(n) removeFirst()
while head < queue.count {
let node = queue[head]
head += 1
for next in neighbors(node) {
// 🔧 Fill in: the "already visited" check — critical to avoid infinite loops.
guard distance[next] == nil else { continue }
distance[next] = distance[node]! + 1 // 🔧 Fill in: whatever update belongs here.
queue.append(next)
}
}
return distance
}The skeleton never changes: a queue seeded with the starting point(s), a visited-check that marks a node the moment it's enqueued (not when it's dequeued — that avoids the same node being queued multiple times), and a loop that processes the queue front-to-back, pushing each unvisited neighbor once. Multi-source BFS is the same skeleton with more than one node seeded into the queue at distance 0.
Rotting Oranges — a grid where 2 = rotten orange, 1 = fresh orange, 0 = empty cell. Every minute, a rotten orange rots all 4-directionally adjacent fresh oranges. Return the minimum minutes until no fresh orange remains, or -1 if that's impossible.
func orangesRotting(_ grid: [[Int]]) -> Int {
var grid = grid
let rows = grid.count
let cols = grid[0].count
var queue: [(Int, Int)] = []
var freshCount = 0
// Multi-source seed: every already-rotten orange starts in the queue at minute 0.
for r in 0..<rows {
for c in 0..<cols {
if grid[r][c] == 2 { queue.append((r, c)) }
if grid[r][c] == 1 { freshCount += 1 }
}
}
var minutes = 0
var head = 0
let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while head < queue.count {
let levelSize = queue.count - head // everything currently in the queue is THIS minute's ring
var rottedThisRound = false
for _ in 0..<levelSize {
let (r, c) = queue[head]
head += 1
for (dr, dc) in directions {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols, grid[nr][nc] == 1 else { continue }
grid[nr][nc] = 2
freshCount -= 1
queue.append((nr, nc))
rottedThisRound = true
}
}
if rottedThisRound { minutes += 1 }
}
return freshCount == 0 ? minutes : -1
}
// smoke test
print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]])) // 4
print(orangesRotting([[2,1,1],[0,1,1],[1,0,1]])) // -1
print(orangesRotting([[0,2]])) // 0Mapped onto the template: queue is seeded with every rotten orange at once instead of a single start — that's multi-source BFS. The "already visited" guard is folded into the grid check grid[nr][nc] == 1 (a cell that's already 2 or 0 is implicitly skipped). The levelSize trick — snapshotting how many entries belong to the current ring before processing them — is what lets the code count minutes per BFS layer instead of per individual node, directly mirroring the "process one full ring before moving to the next" guarantee from the diagram.
BFS is a ripple spreading across a pond — it touches everything at the current distance before anything farther away, which is exactly why the first ripple to reach a point proves that's the shortest distance to it.
A problem gives you a binary tree and asks for the "average value of nodes on each level, returned as an array." Explain how BFS's queue naturally gives you level boundaries without needing to store depth explicitly on each node — and contrast that with why DFS would need extra bookkeeping (like passing a depth parameter) to group nodes by level.
⬅️ Previous: DFS and Backtracking · Next: Topological Sort ➡️