Reconstruct a route from first parents

A traversal order answers “what did the algorithm inspect?” A path answers “which legal moves connect start to goal?” Those are different sequences. BFS can expand two sibling cells consecutively even though no edge connects those siblings.

Use the first-parent tree. Starting at the goal, look up its predecessor, then that predecessor’s predecessor, until reaching the requested start. This builds goal-to-start order, so reverse it before returning.

The root has parent None. A chain that reaches None before the requested start is disconnected from that start. A reference to a missing entry is also disconnected. If the goal is absent, there is no discovered route to reconstruct.

Start equal to goal is not an empty route: when present, its path contains one vertex and zero edges. This distinction makes distance calculations consistent.

parents = {"S":None, "A":"S", "B":"S", "G":"A"}
node, path = "G", []
while node is not None:
    path.append(node)
    node = parents[node]
print("backward", path)
print("route", list(reversed(path)))

A malformed parent map can contain a self-loop or a longer cycle. Track a local seen set. Encountering a repeated coordinate raises ValueError instead of hanging. Search-generated trees should never have that structure, but a reusable helper benefits from a clear failure mode.

This helper has no grid argument, so it cannot independently establish that every edge is legal. The search tests check each parent against neighbors; the visualizer checks uploaded route adjacency. A chain of arbitrary coordinates can be structurally connected without being a legal path through a particular board.

On the fork fixture, BFS returns three vertices and DFS nine. Both are valid; only BFS has the minimum-edge guarantee under our equal-cost assumptions. Subtract one from path length to count moves.

expanded = ["S", "A", "B", "G"]
parents = {"S":None, "A":"S", "B":"S", "G":"A"}
print("previous expansion", expanded[-2])
print("goal parent", parents["G"])
print("route moves", len(["S","A","G"]) - 1)

Complete the parent walk and test a normal route, an absent goal, an early None, a missing intermediate entry and both self/longer cycles. Keep the map unchanged.

Next we combine the searches with reconstruction and make unreachable goals an ordinary result rather than an exception or an endless loop.