Breadth-first search answers a very specific question very well: what’s the fewest number of steps from here to there? Fewest moves to escape a maze, fewest friend-of-a-friend hops between two people, fewest word changes to turn cold into warm, fewest minutes for rot to spread through a crate of oranges. Whenever every move costs the same, BFS gives the shortest path, and it does it in time proportional to the size of the graph.
The algorithm is short. The things worth getting right are why it’s correct, where to mark nodes as visited, and when it stops being the right tool.
Rings of distance
BFS starts at the source and explores outward in rings. First the source itself (distance 0), then everything one step away, then everything two steps away, and so on. A first-in, first-out queue is what enforces that order. You dequeue a node, enqueue its undiscovered neighbours at the back, and because the queue is FIFO, every node at distance d is processed before any node at distance d + 1.
That ordering is the correctness argument. At any moment the queue holds nodes from at most two consecutive distances, d followed by d + 1. When BFS discovers a node for the first time, it’s discovering it from a node at the smallest distance that can reach it, so the distance it records (parent’s distance plus one) is the shortest possible. Any other path to that node would come from a node processed later, which is at the same distance or further, so it can’t be shorter. First discovery is final.
Escaping a maze
Here’s a grid maze. S is the start, E is the exit, # is a wall, and you can move up, down, left or right:
S.#.....
.##.###.
....#...
.##...#EThe BFS below stores, for each discovered cell, the cell it was discovered from. That parent map does two jobs: it’s the visited set, and at the end it lets you walk backwards from the exit to rebuild the actual path.
from collections import deque
def shortest_path(maze):
rows, cols = len(maze), len(maze[0])
start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
goal = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "E")
parent = {start: None} # doubles as the visited set
queue = deque([start])
while queue:
r, c = queue.popleft()
if (r, c) == goal:
break
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in parent:
parent[(nr, nc)] = (r, c) # mark when enqueued
queue.append((nr, nc))
if goal not in parent:
return None
path, node = [], goal
while node is not None: # walk parents back to the start
path.append(node)
node = parent[node]
return path[::-1]Running it and drawing the path with *:
steps: 12
S.#.....
*##.###.
****#***
.##***#EThe route goes down, along row 2, dips into row 3 to get around the wall at column 4, climbs back to row 2 and drops to the exit. There are other 12-step routes; BFS returns whichever one the neighbour order finds first, and all of them are shortest. On a maze where the exit is walled off, the function returns None, because the queue empties before the goal is ever discovered.
Use collections.deque and popleft(). A Python list with pop(0) shifts every remaining element on each call, which quietly turns this O(V + E) algorithm into an O(V²) one on large graphs. The Big-O note has timings for exactly that mistake.
Mark on enqueue, not on dequeue
The most common BFS bug is marking a node as visited when you take it out of the queue instead of when you put it in. Between those two moments, other nodes can discover it and enqueue it again. Counting queue pushes on open grids with no walls shows the effect:
10x10 open grid (100 cells): mark on enqueue 100 pushes, mark on dequeue 181 pushes
100x100 open grid (10,000 cells): mark on enqueue 10,000 pushes, mark on dequeue 19,801 pushes
300x300 open grid (90,000 cells): mark on enqueue 90,000 pushes, mark on dequeue 179,401 pushesMarking on dequeue, with a continue to skip copies that were already processed, still gives the right distances but nearly doubles the queue traffic on a grid. In a dense graph, where a node can be discovered from many neighbours, the waste grows to O(E) queue entries instead of O(V).
It gets much worse if the dequeue version also forgets to skip duplicates, so every copy gets expanded again:
5x5: mark on dequeue, no skip: 251 pushes
10x10: mark on dequeue, no skip: 184,755 pushes
15x15: mark on dequeue, no skip: over 5,000,000 pushesA 10 by 10 grid, 100 cells, generates 184,755 queue entries, and the count explodes from there. That’s how a BFS that “works on the examples” times out on the hidden tests. Mark when you enqueue, and each node enters the queue exactly once.
One level at a time
Many problems need to know which ring you’re in, not just the distance to one target: the minimum depth of a tree, the rightmost node on each level, the number of minutes for something to spread. The standard trick is to read len(queue) at the start of each round. At that moment the queue holds exactly one level, so processing that many nodes finishes the level, and anything enqueued meanwhile belongs to the next one.
That’s the backbone of Binary Tree Level Order Traversal and Binary Tree Right Side View, and of the practice problem below.
Where BFS stops being correct
The argument that “first discovery is final” depends on every edge costing the same. Give edges different weights and it falls apart. Here are travel times between four road junctions:
roads = { # minutes between junctions
"A": [("D", 30), ("B", 5)],
"B": [("C", 5)],
"C": [("D", 5)],
"D": [],
}BFS edges A->D: 1
BFS 'minutes' A->D: 30
Dijkstra minutes A->D: 15BFS correctly reports that D is one edge from A. But if you add up minutes during the BFS, it locks in 30 for D, because it discovers D directly from A before ever exploring the route through B and C, which takes 15 minutes. Dijkstra’s algorithm fixes this by replacing the FIFO queue with a priority queue ordered by total cost, so it always expands the cheapest frontier node next. If weights are only 0 or 1, a deque-based “0-1 BFS” (push 0-weight edges to the front, 1-weight edges to the back) gets the same result in linear time.
Complexity for BFS is O(V + E) time: each node is enqueued and dequeued once, and each edge is examined once from each end. On a grid of R rows and C columns, that’s O(R · C). Space is O(V) for the visited set and queue; on a grid the queue’s widest ring is around O(R + C) from a corner start, but the visited set is still O(R · C).
Interview practice: Rotting Oranges
A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, each rotten orange rots its fresh neighbours up, down, left and right. Return the minimum number of minutes until no fresh orange remains, or -1 if some can never rot. For [[2,1,1],[1,1,0],[0,1,1]] the answer is 4.
Answer
This is BFS with many sources. Instead of starting from one cell, put every initially rotten orange into the queue at minute 0. The rings now spread from all of them at once, and the ring number when a fresh orange is reached is the minute it rots, which is the shortest distance from it to any rotten orange. Processing one level per minute with len(queue) gives the count directly. Track how many fresh oranges remain so you can return -1 if some are unreachable.
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c)) # every rotten orange is a source at minute 0
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh:
for _ in range(len(queue)): # exactly one minute's worth of oranges
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark on enqueue
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]),
oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]),
oranges_rotting([[0, 2]]),
oranges_rotting([[2, 1, 1, 1, 1, 1, 2]]))4 -1 0 3The second grid has a fresh orange in the bottom-left corner with empty cells on both open sides, so it can never rot and the answer is -1. The third has nothing fresh, so the loop never runs and the answer is 0; checking fresh in the loop condition is what avoids counting an extra minute there. The last case shows why multi-source matters: two rotten oranges at opposite ends of a row of five fresh ones meet in the middle after 3 minutes, whereas running BFS from each source separately and combining the results would be slower and fiddlier.
Time is O(R · C), since each cell is enqueued at most once; space is O(R · C) for the queue in the worst case. The grid itself is the visited set here (setting a cell to 2 marks it), which saves memory but modifies the input; say so, and copy the grid first if the caller needs it intact. Try it on Rotting Oranges, then Number of Islands, which runs one BFS per unvisited land cell.
Continue with
- Data Structures and Algorithms interview questions
- DSA multiple-choice questions
- Graph DFS States and Cycle Detection, the depth-first counterpart
- Tree Traversals and Information Flow
- MIT 6.006 Introduction to Algorithms (Spring 2020), lecture 9 covers breadth-first search and lecture 13 Dijkstra