The Intuition: Exploring in Rings
Imagine dropping a stone into a pond. The ripple reaches the closest points first, then spreads outward in expanding rings. BFS explores a graph the same way: starting from one node, it visits every node one step away, then every node two steps away, and so on. It never jumps ahead to a distant node while closer ones remain unexplored.
This 'closest first' order is the whole point. Because BFS fans out evenly in every direction, the first time it reaches a node it has arrived by the fewest possible edges. That single property is what makes BFS the natural tool for shortest-path questions in unweighted graphs — and it is much easier to see once you watch the frontier expand one layer at a time.
The Mechanics: A Queue and a Visited Set
BFS needs two pieces of state: a queue of nodes waiting to be visited, and a set of nodes already seen. You start by putting the source node in the queue and marking it visited. Then you loop: remove the node at the front of the queue, look at each of its neighbors, and for any neighbor you have not seen, mark it visited and add it to the back of the queue.
The queue is what enforces level order. Because it is first-in-first-out, nodes are processed in the order they were discovered, so an entire layer is drained before the next begins. The visited set is equally essential: without it, a cycle in the graph would send BFS around the same nodes forever. Mark a node visited when you enqueue it, not when you dequeue it, or the same node can land in the queue several times.
Finding the Shortest Path
To turn traversal into shortest-path, remember where each node was reached from. Keep a parent (or 'came from') map: when you discover a neighbor, record which node you reached it from. Once you arrive at the target, follow the parent pointers backward to reconstruct the route, then reverse it. The number of edges on that route is the node's distance from the source.
This works only because the graph is unweighted — every edge counts as one step. If edges have different weights, BFS can be wrong, because a path with more edges might have a smaller total weight. For weighted graphs you need Dijkstra's algorithm (or 0-1 BFS when weights are only 0 and 1). BFS is the unweighted special case where those algorithms all agree.
from collections import deque
def bfs_shortest_path(graph, start, goal):
"""Return the shortest path (fewest edges) from start to goal."""
queue = deque([start])
parent = {start: None} # also serves as the visited set
while queue:
node = queue.popleft()
if node == goal:
path = []
while node is not None:
path.append(node)
node = parent[node]
return path[::-1] # reverse: start -> goal
for neighbor in graph[node]:
if neighbor not in parent: # not yet visited
parent[neighbor] = node
queue.append(neighbor)
return None # goal unreachableV is the number of vertices and E the number of edges. Using an adjacency list, BFS dequeues each vertex once and examines each edge once (twice for undirected graphs), so it is O(V + E) in the best, average, and worst cases — it may have to explore the whole reachable graph. Space is O(V) for the queue and visited set. With an adjacency matrix, time rises to O(V^2).
When to use it
- Finding the shortest path or fewest moves in an unweighted graph or grid — mazes, word ladders, or a knight's moves on a chessboard.
- Computing the minimum number of steps to reach a target state, or listing every node within k steps of a source.
- Level-order traversal of a tree, or processing any graph one layer at a time.
- Testing reachability and finding connected components — whether two nodes are connected at all.
Watch out for
- Marking a node visited when you dequeue it instead of when you enqueue it. The same node can then be added to the queue multiple times, wasting work and sometimes corrupting the computed distances.
- Using a plain list and popping from the front with list.pop(0), which is O(n) and quietly makes the whole traversal O(V^2). Use a real FIFO queue like collections.deque.
- Running BFS on a weighted graph and expecting shortest paths. BFS counts edges, not total weight — once edges have different costs you need Dijkstra's algorithm instead.
BFS is one of the most frequently tested graph patterns in coding interviews, especially for anything phrased as 'shortest', 'fewest steps', 'minimum moves', or 'nearest'. Classic problems include number of islands, rotting oranges, word ladder, and shortest path in a binary matrix — many of which are grids where the graph is implicit and a cell's neighbors are the adjacent cells. Interviewers watch for whether you reach for BFS (not DFS) the moment 'shortest path in an unweighted graph' appears, whether you mark nodes visited at enqueue time, and whether you use an O(1) queue rather than popping from the front of a list. Being able to explain why BFS yields the shortest path — the level-by-level frontier — matters as much as writing the loop correctly.