Use a queue for breadth-first search

Breadth-first search expands the oldest scheduled work first. On an unweighted graph, that means expanding distance-zero cells, then distance-one cells, then distance-two cells. A FIFO queue supplies this ordering.

The shortest-path statement has assumptions: every move costs one, the goal is reachable, and discovery records the first parent without later overwrites. It is a minimum number of edges, not the least physical travel time when moves have different costs.

Use collections.deque for a queue. append adds to the right; popleft removes from the left. list.pop(0) shifts the remaining elements and is an avoidable cost for large queues.

Mark discovery and assign the parent before appending a neighbor. Otherwise two current cells can schedule the same neighbor. Stop when the goal is removed for expansion. Other frontier work may remain; that does not invalidate the found route.

from collections import deque
frontier = deque(["start"])
frontier.extend(["right", "down"])
print(frontier.popleft())
print(list(frontier))

FIFO order establishes the shortest-edge-count property: every newly discovered neighbor of a distance-k cell has distance k+1, and older layers are removed first. Equal-length alternatives are resolved by neighbor order, not by a unique mathematical answer.

On our fork fixture, the goal lies two moves down from the start while a longer route circles right. BFS retains the two-edge parent chain. This concrete counterexample will also show why DFS makes a different promise.

A textbook adjacency-list search runs in O(V+E) time with O(V) discovery storage. This bounded teaching lab additionally validates grid calls and copies growing trace snapshots. Those costs can make the full exported run O(V²) in time and trace storage. The 16 × 16 limit keeps it inspectable; for larger graphs, validate once and stream small events instead.

parents = {"start":None}
for current, other in [("start","A"),("start","B"),("B","A")]:
    if other not in parents:
        parents[other] = current
print(parents)

Complete the search and inspect the ready, expansion and done snapshots. A one-cell start/goal should expand once; an isolated start with a different goal should exhaust its frontier. Check every non-root parent is an actual legal neighbor and every expanded cell appears only once.

The next path lesson follows these parent links. It does not infer a route by drawing lines through the expansion sequence.