Loading learning content...
In the previous page, we established that BFS computes shortest distances in unweighted graphs. But in most practical applications, knowing the distance isn't enough—we need the actual path. When navigating a maze, you don't just want to know it takes 15 steps; you want the step-by-step directions.
Parent tracking is the elegant technique that transforms BFS from a distance-computing algorithm into a path-finding algorithm. The idea is simple but powerful: as we discover each vertex, we record which vertex led us there. This creates a trail of breadcrumbs that we can follow backward from destination to source, recovering the entire shortest path.
By the end of this page, you will understand how to augment BFS with parent tracking to reconstruct shortest paths. You'll learn to initialize and update the parent array, trace from destination to source, reverse the path for correct ordering, and handle edge cases like unreachable vertices.
Definition:
A parent array (also called parent map or predecessor array) is a data structure that maps each vertex to the vertex from which it was discovered during BFS traversal.
parent[v] = u means: "vertex v was discovered from vertex u"
Key Properties:
The BFS Tree:
When BFS runs from a source vertex, the parent pointers collectively form a tree structure rooted at the source. This tree has special properties:
This is why the tree is called a shortest path tree or BFS tree. It encodes all shortest paths from the source to every reachable vertex.
In the original graph, a vertex might have multiple paths from the source. But each vertex has exactly ONE parent in BFS because the first discovery determines the parent, and we mark vertices visited to prevent rediscovery. This ensures the parent relationship is a function (each vertex maps to exactly one parent), creating a tree structure.
Adding parent tracking to BFS requires only minor modifications:
parent[source] = null or a sentinel valuev is discovered from vertex u, set parent[v] = uLet's see the complete algorithm:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
interface Graph { adjacencyList: Map<number, number[]>;} function bfsWithPath(graph: Graph, source: number, target: number): number[] | null { const visited = new Set<number>(); const parent = new Map<number, number | null>(); const queue: number[] = []; // Initialize: source has no parent visited.add(source); parent.set(source, null); queue.push(source); while (queue.length > 0) { const current = queue.shift()!; // Early termination: found target if (current === target) { return reconstructPath(parent, source, target); } // Explore neighbors for (const neighbor of graph.adjacencyList.get(current) || []) { if (!visited.has(neighbor)) { visited.add(neighbor); parent.set(neighbor, current); // KEY: Record parent queue.push(neighbor); } } } // Target not reachable return null;} function reconstructPath( parent: Map<number, number | null>, source: number, target: number): number[] { const path: number[] = []; let current: number | null = target; // Trace back from target to source while (current !== null) { path.push(current); current = parent.get(current) ?? null; } // Reverse to get path from source to target return path.reverse();}When searching for a path to a specific target, we can return immediately upon finding the target. Since BFS guarantees the first path found is shortest, continuing after finding the target is unnecessary. This optimization can significantly speed up queries where the target is relatively close.
Let's trace through path reconstruction step by step to build solid intuition.
Example Scenario:
Consider a graph with the following shortest path from S to G:
S → A → D → G
After BFS completes, the parent map contains:
parent[S] = null (source)
parent[A] = S
parent[D] = A
parent[G] = D
Reconstruction Trace:
| Step | Current Vertex | Action | Path (so far) |
|---|---|---|---|
| 1 | G | Start at target, add to path | [G] |
| 2 | D (parent of G) | Move to parent, add to path | [G, D] |
| 3 | A (parent of D) | Move to parent, add to path | [G, D, A] |
| 4 | S (parent of A) | Move to parent, add to path | [G, D, A, S] |
| 5 | null (parent of S) | Stop: reached source | [G, D, A, S] |
| 6 | — | Reverse the path | [S, A, D, G] |
Result: The shortest path is S → A → D → G
Why Do We Build Backward Then Reverse?
This is a deliberate design choice with practical implications:
Option 1: Build backward, then reverse (recommended)
Option 2: Build forward using prepend
The backward-then-reverse approach is more efficient for array-based path storage. If using a data structure with O(1) prepend (like a deque), both approaches are equivalent.
A common mistake is prepending elements to an array/list during reconstruction. In most languages, array prepend is O(n), making the reconstruction O(n²) instead of O(n). Always append then reverse, or use a data structure with O(1) prepend like a deque/linked list.
Robust implementations must handle several edge cases gracefully.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
function robustBFSPath( graph: Map<number, number[]>, source: number, target: number): { path: number[] | null; distance: number } { // Edge case: source equals target if (source === target) { return { path: [source], distance: 0 }; } // Edge case: source not in graph if (!graph.has(source)) { return { path: null, distance: -1 }; } const visited = new Set<number>(); const parent = new Map<number, number | null>(); const distance = new Map<number, number>(); const queue: number[] = []; visited.add(source); parent.set(source, null); distance.set(source, 0); queue.push(source); while (queue.length > 0) { const current = queue.shift()!; const currentDist = distance.get(current)!; for (const neighbor of graph.get(current) || []) { if (!visited.has(neighbor)) { visited.add(neighbor); parent.set(neighbor, current); distance.set(neighbor, currentDist + 1); queue.push(neighbor); // Early termination when target found if (neighbor === target) { const path = reconstructPath(parent, target); return { path, distance: distance.get(target)! }; } } } } // Target not reachable return { path: null, distance: -1 };} function reconstructPath( parent: Map<number, number | null>, target: number): number[] { const path: number[] = []; let current: number | null = target; while (current !== null) { path.push(current); current = parent.get(current) ?? null; } return path.reverse();}Parent tracking has memory implications that are important in large-scale applications.
| Data Structure | Memory | Purpose |
|---|---|---|
| Visited set | O(V) | Track which vertices have been seen |
| Parent map/array | O(V) | Store parent for each reachable vertex |
| Queue | O(V) worst case | Frontier of exploration |
| Reconstructed path | O(path length) | The output path |
| Total | O(V) | Linear in number of vertices |
Array vs Map for Parent Storage:
When vertices are integers in a contiguous range [0, V-1], use an array:
const parent: (number | null)[] = new Array(V).fill(null);
// O(1) access, O(V) memory allocated upfront
When vertices are arbitrary objects (strings, tuples, objects), use a map:
const parent = new Map<string, string | null>();
// O(1) average access, memory grows with discoveries
Space Optimization: When Parent Tracking Isn't Needed
If you only need the shortest distance (not the path), you can skip parent tracking entirely. This saves the O(V) memory for the parent array. However, in most practical applications, you will want the actual path, making parent tracking essential.
For very large graphs with a specific source and target, bidirectional BFS can dramatically reduce memory usage. It runs BFS simultaneously from source and target, meeting in the middle. This reduces the explored space from O(b^d) to O(2 × b^(d/2)) = O(b^(d/2)), where b is branching factor and d is distance. Parent tracking works in both directions, then paths are joined at the meeting point.
An important subtlety: there may be multiple shortest paths of the same length between source and target. Standard BFS parent tracking finds one of them—specifically, the one determined by the order in which neighbors are explored.
Example:
Consider a graph where both paths have length 3:
BFS might discover C from either A or B first, depending on:
The parent of C will be whichever was discovered first, determining which path is reconstructed.
Finding All Shortest Paths:
To find ALL shortest paths, we need a modified approach:
parent[v] = u, use parents[v] = [list of all parents]12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
function allShortestPaths( graph: Map<number, number[]>, source: number, target: number): number[][] { if (source === target) return [[source]]; const distance = new Map<number, number>(); const parents = new Map<number, number[]>(); const queue: number[] = []; distance.set(source, 0); parents.set(source, []); queue.push(source); while (queue.length > 0) { const current = queue.shift()!; const currentDist = distance.get(current)!; // Stop if we've passed the target's level if (distance.has(target) && currentDist >= distance.get(target)!) { continue; } for (const neighbor of graph.get(current) || []) { const neighborDist = distance.get(neighbor); if (neighborDist === undefined) { // First discovery distance.set(neighbor, currentDist + 1); parents.set(neighbor, [current]); queue.push(neighbor); } else if (neighborDist === currentDist + 1) { // Same shortest distance via different path parents.get(neighbor)!.push(current); } } } if (!distance.has(target)) return []; // Reconstruct all paths via DFS on parent graph return reconstructAllPaths(parents, source, target);} function reconstructAllPaths( parents: Map<number, number[]>, source: number, target: number): number[][] { const allPaths: number[][] = []; function dfs(current: number, path: number[]) { path.push(current); if (current === source) { allPaths.push([...path].reverse()); } else { for (const parent of parents.get(current) || []) { dfs(parent, path); } } path.pop(); } dfs(target, []); return allPaths;}The number of shortest paths can be exponential! In a grid, the number of shortest paths from corner to corner is C(2n, n) = O(4^n / √n). Only enumerate all paths when you truly need them all, and be aware of the potential explosion in output size.
Let's examine common patterns and variations you'll encounter in real problems.
Grid-based pathfinding is one of the most common applications. Vertices are grid cells, and edges connect adjacent cells.
Key adaptations:
Map<string, string> where keys are "row,col" stringsparent[row][col] = [prevRow, prevCol]12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
type Point = [number, number]; const DIRECTIONS: Point[] = [ [0, 1], [0, -1], [1, 0], [-1, 0]]; function gridBFSPath( grid: number[][], start: Point, end: Point): Point[] | null { const rows = grid.length; const cols = grid[0].length; const key = (r: number, c: number) => `${r},${c}`; const visited = new Set<string>(); const parent = new Map<string, Point | null>(); const queue: Point[] = []; visited.add(key(start[0], start[1])); parent.set(key(start[0], start[1]), null); queue.push(start); while (queue.length > 0) { const [row, col] = queue.shift()!; if (row === end[0] && col === end[1]) { // Reconstruct path const path: Point[] = []; let curr: Point | null = end; while (curr) { path.push(curr); curr = parent.get(key(curr[0], curr[1])) ?? null; } return path.reverse(); } for (const [dr, dc] of DIRECTIONS) { const nr = row + dr; const nc = col + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 0 && // 0 = passable !visited.has(key(nr, nc))) { visited.add(key(nr, nc)); parent.set(key(nr, nc), [row, col]); queue.push([nr, nc]); } } } return null; // No path exists}Let's consolidate what we've learned about parent tracking:
What's Next:
With parent tracking mastered, we now turn to the distance array—a complementary technique that tracks the shortest distance from the source to every vertex. While parent tracking enables path reconstruction, the distance array enables efficient distance queries and serves as the foundation for more advanced algorithms like Dijkstra's.
You now understand how to augment BFS with parent tracking to reconstruct the actual shortest path, not just compute its length. This technique is fundamental to practical pathfinding applications—from game AI to network routing to puzzle solvers. Next, we'll explore the distance array and its role in BFS.