Pattern 5: BFS on a grid (shortest path)
DFS goes deep along a path before coming back. BFS does the opposite: it explores in layers, like concentric waves from the starting point. That order is exactly what answers "what is the shortest path?".
Try it first: Shortest Path in Binary Matrix
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
In an n × n grid of 0 (free) and 1 (blocked), return the length of the shortest path from the top-left corner to the bottom-right corner, moving in the 8 directions through 0 cells. If there is none, return -1. (The length counts the visited cells, start and end included.)
Example: [[0,0,0],[1,1,0],[1,1,0]] → 4.
Tried it? If you tried a DFS, you noticed it finds a path, not necessarily the shortest one. The theory below shows why breadth-first search (BFS) solves "the shortest" naturally.
The theory: exploring in layers with a queue
BFS uses a queue (FIFO: first in is first out). You start at the initial cell (distance 1), and at each step you take the oldest one out of the queue and add its not-yet-visited neighbors (with distance + 1).
queue = [(start, distance 1)]; mark start as visited
while the queue is not empty:
(r, c, d) = take the oldest out of the queue
if (r,c) is the destination → return d (first to arrive = shortest!)
for each free, unvisited neighbor:
mark as visited
add to the queue with distance d + 1
The magic: since the queue processes all the cells at distance d before
any at distance d+1, the search advances in layers. The first moment the
destination comes out of the queue, it arrived by the shortest path — there is
no shorter route, otherwise it would have been processed earlier.
Compare the two searches on the same open grid. BFS — notice how the current cell jumps in "rings" ever farther from the origin:
And the DFS from lesson 4, for contrast — it dives deep in one direction before coming back:
Why is it O(m·n) and why does it give the shortest path?
- Time: each cell enters the queue at most once (we mark visited when enqueuing, not when dequeuing — a detail that avoids duplicates). For each one, we look at a constant number of neighbors → O(m·n). Space O(m·n) (queue + visited).
- Shortest: BFS expands by increasing distance. In an unweighted graph (each step "costs 1"), the first time the destination is reached is, necessarily, by the fewest steps.
A detail that causes bugs: mark the neighbor as visited at the moment you enqueue it, not when it leaves the queue. Otherwise, the same cell can be added several times (by different neighbors) before being processed, inflating the queue and even breaking the count.
DFS or BFS? The question decides
Both traverse everything that is connected and cost O(m·n). The choice depends on the question:
| The question is... | Use | Why |
|---|---|---|
| "does it exist? how many? cover the region" | DFS (simpler to write) | the order does not matter |
| "what is the shortest path? fewest steps?" | BFS | expands by increasing distance |
| "all paths / a specific path" | backtracking (DFS + undo) | needs to explore and come back |
🧠 Review quiz
0/41. Why does BFS find the shortest path in an unweighted grid?
2. What is the behavioral difference between DFS and BFS in exploration?
3. Why mark the cell as visited when ENQUEUING it (and not when dequeuing)?
4. You need the FEWEST number of steps to get out of a grid maze. DFS or BFS?
Summary
- BFS uses a queue and explores in layers of increasing distance.
- In an unweighted graph, the first arrival at the destination is the shortest path.
- Mark visited when enqueuing; O(m·n) time and space.
- DFS for "exists/cover", BFS for "shortest", backtracking for "all paths".
Last stop: the synthesis of the Matrix section and the quiz before the exam.