BFS Template
The Intuition
Imagine dropping a stone into a still pond. The first ripple ring contains every point exactly one step from where the stone landed. The second ring contains everything two steps away. The third ring, three steps. Ripples never skip ahead. They expand outward one layer at a time, perfectly ordered by distance.
BFS works the same way. You start at a node, and your queue holds the current ripple ring. You process every node in ring 1 before you even begin to look at ring 2. When you pull a node off the front of the queue, its neighbors go to the back. Since the queue is first-in-first-out, all of ring 1 gets processed before any of ring 2's neighbors. All of ring 2 finishes before ring 3 starts. The queue naturally maintains this order without you doing anything special.
Here's why that matters: the first time you reach any node is guaranteed to be the shortest path. You can't accidentally find a longer path first, because shorter paths are always explored before longer ones. If your target is 5 steps away, BFS will find it in exactly 5 steps. It won't waste time exploring a 20-step detour and then backtrack.
For grids, the same logic applies. Each cell is a "node," and its four neighbors (up, down, left, right) are its "edges." Drop your stone at the starting cell, and the ripple expands outward. Mark cells as visited when you add them to the queue, not when you process them. If you wait until processing, multiple ripple rings might add the same cell, and you'll end up doing extra work.
Shortest path in unweighted graphs, level-order traversal, minimum moves/steps problems, flood fill, word ladder, or any problem asking for the minimum number of operations.
- Weighted edges (use Dijkstra)
- Need to explore all paths not just shortest (use DFS)
- Graph is very deep but narrow (DFS uses less memory)
Variations:
- Graph BFS: Standard adjacency list traversal.
- Grid BFS: Treat 2D grid cells as graph nodes with 4-directional edges.
- Multi-source BFS: Start with multiple sources in the queue simultaneously (e.g., "rotting oranges").
- start equals end
- unreachable target
- single node
Key Points
- •Use a queue (FIFO) to process nodes level by level
- •Mark nodes as visited before enqueueing to avoid duplicates
- •Track distance/level with a counter or tuple in the queue
- •Guarantees shortest path in unweighted graphs
- •Can be applied to grids by treating cells as nodes
Code Template
1 from collections import deque
2
3 def bfs(graph, start):
4 """BFS traversal of adjacency list graph."""
5 visited = {start}
6 queue = deque([start])
7
8 while queue:
9 node = queue.popleft()
10 # process(node)
11
12 for neighbor in graph[node]:
13 if neighbor not in visited:
14 visited.add(neighbor)
15 queue.append(neighbor)
16
17 def bfs_shortest_path(graph, start, end):
18 """Find shortest path in unweighted graph."""
19 visited = {start}
20 queue = deque([(start, [start])])
21
22 while queue:
23 node, path = queue.popleft()
24 if node == end:
25 return path
26
27 for neighbor in graph[node]:
28 if neighbor not in visited:
29 visited.add(neighbor)
30 queue.append((neighbor, path + [neighbor]))
31
32 return []
33
34 def bfs_grid(grid, start_r, start_c):
35 """BFS on a 2D grid."""
36 rows, cols = len(grid), len(grid[0])
37 visited = {(start_r, start_c)}
38 queue = deque([(start_r, start_c, 0)]) # row, col, distance
39 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
40
41 while queue:
42 r, c, dist = queue.popleft()
43 for dr, dc in directions:
44 nr, nc = r + dr, c + dc
45 if (0 <= nr < rows and 0 <= nc < cols
46 and (nr, nc) not in visited
47 and grid[nr][nc] != '#'):
48 visited.add((nr, nc))
49 queue.append((nr, nc, dist + 1))Common Mistakes
- Marking visited after dequeue instead of before enqueue (causes duplicates)
- Not handling disconnected components
- Forgetting to check bounds in grid BFS