Graph BFS — shortest paths on unweighted graphs
Graph BFS
Breadth-first search visits a graph in expanding rings: start node first, then everything one edge away, then two. That layered order is the whole point — on an unweighted graph, the first time BFS reaches a node, it did so along the shortest possible path.
The pattern
Three things: a queue (collections.deque — list.pop(0) is O(n) and will silently tank runtime), a visited set, and optionally a parent map for path reconstruction.
Why 'mark on enqueue' matters
If you only add to seen when a node is dequeued, the same node can be enqueued many times before its first pop. On a dense graph this explodes memory. Rule: the moment a node is pushed onto the queue, it's visited.
Shortest path
Track parent[v] = u at the same moment you mark v as seen. When you reach the destination, walk the parent chain backwards and reverse.
Common bugs to avoid
- Using a list as a queue.
.pop(0)is O(n). - Marking visited on dequeue. Duplicates flood the queue.
- BFS on a weighted graph. Reach for Dijkstra instead.
Try it
- Add a
bfs_distances(start)that returns a dict mapping every reachable node to its distance fromstart. - Extend the graph with an isolated pair and confirm
shortest_path(0, 7)returnsNonewithout hanging.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Write
bfs_order(graph, start)that returns the list of nodes in the order BFS visits them starting fromstart. Iterate each node's neighbors in the order they appear in the adjacency list. - Exercise 2
Write
shortest_hops(graph, start, target)that returns the minimum number of edges betweenstartandtargetin an unweighted graph, or -1 if unreachable.start == targetshould give 0. - Exercise 3
Write
levels(graph, start)that returns a list of lists, where index i holds every node whose shortest distance fromstartis exactly i. Within a level, keep the order BFS discovered the nodes.