Introduction

Breadth-first search can tell you whether a target is reachable, but it can also recover the exact shortest path in an unweighted graph. The missing ingredient is a parent map that remembers how each discovered node was reached.

That is the core idea: BFS explores level by level, and each time it discovers a new node, it stores the predecessor that led to it. Once the target is found, you walk backward through those predecessors and reverse the result.

Why BFS Finds the Shortest Path

In an unweighted graph, BFS visits nodes in order of increasing distance from the start. That means the first time BFS reaches a node, it has already found the shortest path to that node in terms of number of edges.

So if you store the parent at discovery time, the recorded parent chain for the goal corresponds to a shortest path.

Store Parents While Exploring

Here is a complete Python example:

1from collections import deque
2
3
4def bfs_path(graph, start, goal):
5    queue = deque([start])
6    visited = {start}
7    parent = {start: None}
8
9    while queue:
10        node = queue.popleft()
11
12        if node == goal:
13            break
14
15        for neighbor in graph[node]:
16            if neighbor not in visited:
17                visited.add(neighbor)
18                parent[neighbor] = node
19                queue.append(neighbor)
20
21    if goal not in parent:
22        return None
23
24    path = []
25    current = goal
26    while current is not None:
27        path.append(current)
28        current = parent[current]
29
30    path.reverse()
31    return path
32
33
34graph = {
35    "A": ["B", "C"],
36    "B": ["A", "D", "E"],
37    "C": ["A", "F"],
38    "D": ["B"],
39    "E": ["B", "F"],
40    "F": ["C", "E"],
41}
42
43print(bfs_path(graph, "A", "F"))

The result is one shortest path, such as ['A', 'C', 'F'].

How the Parent Map Works

Suppose BFS starts at A:

• it discovers B and stores parent['B'] = 'A'
• it discovers C and stores parent['C'] = 'A'
• later it discovers F from C, so it stores parent['F'] = 'C'

Once the goal is found, reconstruction is just repeated parent lookup:

• 'F'
• parent of F is C
• parent of C is A
• parent of A is None

Reverse that sequence and you have the path from start to goal.

Why You Should Mark Visited Early

Notice that the code marks a node as visited when it is enqueued, not when it is dequeued. That matters because it prevents the same node from being added to the queue multiple times from different parents.

If you delay the visited mark, you may overwrite the clean shortest-path parent information or waste work exploring duplicates.

What Happens If There Is No Path

If the goal is unreachable, it never appears in the parent map. That is why the code checks:

if goal not in parent:
    return None

This is a simple and reliable way to distinguish "found a path" from "searched the connected component and never reached the target."

Common Pitfalls

• Running BFS without a parent map and then wondering why only the distance is known.
• Marking nodes visited too late and allowing duplicates into the queue.
• Overwriting parent pointers after a node has already been discovered.
• Forgetting to handle the no-path case explicitly.
• Assuming BFS gives weighted shortest paths. It only guarantees shortest paths in unweighted graphs or graphs with equal edge cost.

Summary

• To recover the actual BFS path, store each node's parent when the node is first discovered.
• BFS guarantees a shortest path in an unweighted graph because it explores by distance layers.
• Reconstruct the path by walking backward from the goal through the parent map.
• Mark nodes visited when they are enqueued, not later.
• If the goal never enters the parent map, no path exists from the chosen start node.