Matrix BFS
Breadth-first search on matrices for shortest path problems. Learn when BFS guarantees optimal paths.
While DFS explores as deep as possible, BFS explores level by level. This property makes BFS ideal for finding the shortest path in unweighted grids.
When to Use BFS vs DFS
| Use Case | BFS | DFS | |----------|-----|-----| | Shortest path (unweighted) | Yes | No | | Explore all paths | No | Yes | | Level-by-level processing | Yes | No | | Memory (wide graphs) | High | Low | | Memory (deep graphs) | Low | High |
Basic BFS on Grid
use std::collections::{HashSet, VecDeque};
fn bfs(grid: &[Vec<i32>], start_row: usize, start_col: usize) {
let rows = grid.len();
let cols = grid[0].len();
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back((start_row, start_col));
visited.insert((start_row, start_col));
let directions = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];
while let Some((r, c)) = queue.pop_front() {
// Process cell (r, c)
for &(dr, dc) in &directions {
let nr = r as i32 + dr;
let nc = c as i32 + dc;
if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
let (nr, nc) = (nr as usize, nc as usize);
if !visited.contains(&(nr, nc)) && grid[nr][nc] == 1 {
visited.insert((nr, nc));
queue.push_back((nr, nc));
}
}
}
}
}
Problem: Shortest Path in Binary Matrix
Find the shortest path from top-left to bottom-right (8-directional):
Grid: Path length: 4
0 1 0 → . .
0 0 0 ↓ ↘ .
1 1 0 . . →
def shortest_path_binary_matrix(grid):
if not grid or grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
n = len(grid)
if n == 1:
return 1
# 8 directions including diagonals
directions = [
(-1, 0), (1, 0), (0, -1), (0, 1),
(-1, -1), (-1, 1), (1, -1), (1, 1)
]
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
while queue:
r, c, dist = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
if (nr, nc) not in visited and grid[nr][nc] == 0:
if nr == n - 1 and nc == n - 1:
return dist + 1
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
Why BFS Gives Shortest Path
BFS explores all cells at distance d before any cell at distance d+1. So the first time we reach the destination, we've found the shortest path.
Problem: Rotting Oranges
Find minimum time for all oranges to rot (multi-source BFS):
0 = empty, 1 = fresh, 2 = rotten
Before: After 1 min: After 2 min:
2 1 1 2 2 1 2 2 2
1 1 0 → 2 1 0 → 2 2 0
0 1 1 0 1 1 0 2 1
After 3 min: After 4 min:
2 2 2 2 2 2
2 2 0 2 2 0
0 2 2 0 2 2
Answer: 4 minutes
def oranges_rotting(grid):
if not grid:
return -1
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh_count = 0
# Find all rotten oranges and count fresh
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_count += 1
if fresh_count == 0:
return 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
minutes = 0
while queue:
# Process all oranges that rot at current minute
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh_count -= 1
queue.append((nr, nc))
if queue:
minutes += 1
return minutes if fresh_count == 0 else -1
Problem: 01 Matrix (Distance to Nearest 0)
Find distance from each cell to the nearest 0:
def update_matrix(mat):
if not mat:
return mat
rows, cols = len(mat), len(mat[0])
queue = deque()
result = [[float('inf')] * cols for _ in range(rows)]
# Multi-source BFS from all 0s
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
result[r][c] = 0
queue.append((r, c))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if result[nr][nc] > result[r][c] + 1:
result[nr][nc] = result[r][c] + 1
queue.append((nr, nc))
return result
Multi-Source BFS
Start BFS from multiple sources simultaneously by adding them all to the queue initially. The distance to each cell is the distance from the nearest source.
Problem: Walls and Gates
Fill each empty room with distance to the nearest gate:
INF = 2147483647
Before: After:
INF -1 0 INF 3 -1 0 1
INF INF INF -1 → 2 2 1 -1
INF -1 INF -1 1 -1 2 -1
0 -1 INF INF 0 -1 3 4
def walls_and_gates(rooms):
if not rooms:
return
INF = 2147483647
rows, cols = len(rooms), len(rooms[0])
queue = deque()
# Start from all gates
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
if rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
Problem: Minimum Knight Moves
Minimum moves for a knight to reach a target:
def min_knight_moves(x, y):
# Knight can move to 8 positions
moves = [
(2, 1), (2, -1), (-2, 1), (-2, -1),
(1, 2), (1, -2), (-1, 2), (-1, -2)
]
# Use absolute values (symmetric)
x, y = abs(x), abs(y)
queue = deque([(0, 0, 0)]) # (row, col, steps)
visited = {(0, 0)}
while queue:
r, c, steps = queue.popleft()
if r == x and c == y:
return steps
for dr, dc in moves:
nr, nc = r + dr, c + dc
# Stay within reasonable bounds
if (nr, nc) not in visited and nr >= -2 and nc >= -2:
visited.add((nr, nc))
queue.append((nr, nc, steps + 1))
return -1
Level-by-Level BFS
Process all nodes at current level before moving to next:
def bfs_by_level(grid, start):
queue = deque([start])
visited = {start}
level = 0
while queue:
level_size = len(queue)
for _ in range(level_size):
r, c = queue.popleft()
# Process cell at current level
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if is_valid(nr, nc) and (nr, nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc))
level += 1 # Move to next level
Time and Space Complexity
- Time: O(rows × cols) — each cell visited once
- Space: O(rows × cols) — for queue and visited set
BFS vs DFS for Grids
| Aspect | BFS | DFS | |--------|-----|-----| | Shortest path | Guaranteed | Not guaranteed | | Memory | Queue (level size) | Stack (path length) | | Implementation | Iterative (queue) | Recursive or stack | | Use case | Distances, levels | Connectivity, paths |
Key Takeaways
- BFS explores level by level, guaranteeing shortest path
- Use multi-source BFS when there are multiple starting points
- Level-by-level processing is useful for distance calculations
- BFS uses more memory than DFS for wide graphs
- Many grid problems involving "minimum distance" use BFS
Matrix BFS is essential for shortest path problems on grids. Recognize when a problem asks for minimum distance or level-order processing—that's your cue to use BFS.