"BFS fans out from the start like a ripple in a pond — finishing everything one step away before anything two steps away. That ripple is exactly why the first time it reaches a place, it got there by the shortest route."
The Algorithm: a Queue and a Visited Set
Breadth-first search is the queue-based frontier from the Stacks & Queues track, now on a real graph. The recipe:
Put the start node in a queue and mark it visited.
Dequeue a node, process it.
For each unvisited neighbor: mark it visited and enqueue it.
Repeat until the queue is empty.
Because a queue is first-in-first-out, you always process nodes in the order you discovered them — which means strictly by distance from the start: all the 1-step-away nodes, then all the 2-step-away, and so on. The frontier expands in rings.
Why It Finds Shortest Paths
That ring-by-ring expansion is BFS's superpower: the first time BFS reaches any node, it arrived by a path with the fewest possible edges. Nothing closer can be discovered later, because BFS exhausts each distance ring before moving outward. So on an unweighted graph, BFS solves shortest path for free — track each node's parent as you go, and you can reconstruct the actual shortest route by walking parents backward from the target. "Fewest moves," "shortest chain of connections," "closest matching node" — all BFS.
BFS uses a queue frontier, expanding in distance-rings from the start. The first time it reaches a node is via a shortest (fewest-edge) path, so BFS solves unweighted shortest path. Always carry a visited set — graphs have cycles.
The Two Bugs Everyone Hits
First: forgetting the visited set. Graphs have cycles, so without marking visited you loop forever (or, with a tree, just do redundant work). Second, subtler: mark visited when you ENQUEUE, not when you dequeue. If you wait until dequeue, the same node can be added to the queue several times by different neighbors before it's ever processed — bloating the queue and sometimes corrupting distances. Mark it the instant it enters the frontier, and each node is enqueued exactly once. These two habits make BFS O(V + E) and correct.
Pippa's Confession
My first BFS marked nodes visited at dequeue time, and on a dense graph the queue ballooned — the same node sat in it five times. Dad's fix was to move one line: mark visited at enqueue. Suddenly each node entered the frontier once and the whole thing was clean O(V+E). It taught me that in graph code, when you mark visited is as important as that you mark it — a one-line placement that's the difference between elegant and quadratic.
Code
BFS shortest path with parent reconstruction·python
from collections import deque
graph = {
"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
"D": ["B"], "E": ["B", "F"], "F": ["C", "E"],
}
def bfs_shortest(graph, start, goal):
"""Shortest path (fewest edges) in an unweighted graph. O(V + E)."""
visited = {start} # mark at ENQUEUE time
parent = {start: None} # to reconstruct the path
q = deque([start])
while q:
node = q.popleft() # FIFO -> explore by distance
if node == goal:
break
for nb in graph[node]:
if nb not in visited:
visited.add(nb) # mark NOW, before it can be re-queued
parent[nb] = node
q.append(nb)
# walk parents backward from goal to rebuild the path
if goal not in parent: return None
path, cur = [], goal
while cur is not None:
path.append(cur); cur = parent[cur]
return path[::-1]
print(bfs_shortest(graph, "A", "F")) # ['A', 'C', 'F'] — 2 edges, the shortest
On the graph A–B, A–C, B–D, C–D, D–E, run BFS from A by hand: list the order nodes are dequeued and the shortest distance from A to each. Then explain why BFS (not DFS) is the correct choice for 'fewest hops between two users in a social network', and what extra data you'd track to return the actual path.
Hint
Dequeue order: A, B, C, D, E; distances A:0, B:1, C:1, D:2, E:3. BFS explores by distance so the first arrival is the fewest hops; DFS could reach D via a longer route first. Track a parent pointer per node to reconstruct the path by walking backward.
Progress
Progress is local-only — sign in to sync across devices.