Data Structures & AlgorithmsGraph Algorithms

Shortest Path — Unweighted Graphs (BFS)

LevelIntermediate

Duration75 mins

TopicGraph Algorithms

2 / 4

Parent Tracking for Path Reconstruction

Beyond Distance: Recovering the Path Itself

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.

What You Will Learn

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.

The Parent Array Concept

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: parent[source] = null — The source has no parent; it's where the search begins parent[v] = u means d(source, v) = d(source, u) + 1 — Each parent is exactly one step closer to the source Following parent pointers leads to source — Starting from any reachable vertex and repeatedly moving to parent eventually reaches the source The parent relationship forms a tree — Called the BFS tree, rooted at the source

Converting Mermaid diagram...

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: Every reachable vertex appears exactly once (as a child of exactly one parent) The depth of a vertex in the tree equals its shortest path distance from source Paths in this tree from root to any vertex are shortest paths in the original graph 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.

Why a Tree and Not a Graph?

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.

Augmenting BFS with Parent Tracking

Adding parent tracking to BFS requires only minor modifications: Initialize: Create a parent array, setting parent[source] = null or a sentinel value On discovery: When vertex v is discovered from vertex u, set parent[v] = u Reconstruct: After BFS, trace from destination back through parents to source Let's see the complete algorithm:

bfs_with_parent_tracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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();
}

Early Termination Optimization

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.

Path Reconstruction Deep Dive

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 \to A \to D \to 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 \to A \to D \to G

Why Do We Build Backward Then Reverse? This is a deliberate design choice with practical implications: Option 1: Build backward, then reverse (recommended) Trace from target to source following parent pointers Natural because parent pointers point toward source Append to end of list: O(1) per step Reverse at the end: O(path length) Total: O(path length) Option 2: Build forward using prepend Trace from target to source Prepend each vertex to front of list List prepend in array: O(path length) per step! Total: O(path length²) — much worse! 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.

Common Mistake: Prepending in Arrays

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.

Handling Edge Cases

Robust implementations must handle several edge cases gracefully.

Critical Edge Cases

•Target not reachable — BFS completes without finding target. Return null/empty to indicate no path exists.
•Source equals target — Path length is 0. Return [source] immediately.
•Disconnected graph — Some vertices have no path from source. Their parent remains unset.
•Empty graph — No vertices. Handle as no path found.
•Source not in graph — Invalid input. Depending on requirements, throw error or return null.

robust_bfs_path
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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();
}

Memory Considerations

Parent tracking has memory implications that are important in large-scale applications.

Memory Usage Analysis
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.

Bidirectional BFS Optimization

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 \times 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.

When Multiple Shortest Paths Exist

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: S \to A \to C \to T S \to B \to C \to T BFS might discover C from either A or B first, depending on: Whether A or B was queued first (depends on order of S's neighbor list) The order of processing when equal in queue 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: Store all parents: Instead of parent[v] = u, use parents[v] = [list of all parents] Continue BFS until we exceed target distance: Don't stop when finding target; finish the current level Recursive reconstruction: DFS through the parent lists to enumerate all paths

all_shortest_paths
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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;
}

Exponential Path Count

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 / \sqrtn). Only enumerate all paths when you truly need them all, and be aware of the potential explosion in output size.

Practical Implementation Patterns

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: Parent storage: Map<string, string> where keys are "row,col" strings Alternatively: 2D array parent[row][col] = [prevRow, prevCol] Directions encoded as coordinate deltas

grid_path_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
}

2 / 4

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(); }

Step

Current Vertex

Action

Path (so far)

Start at target, add to path

[G]

D (parent of G)

Move to parent, add to path

[G, D]

A (parent of D)

Move to parent, add to path

[G, D, A]

S (parent of A)

Move to parent, add to path

[G, D, A, S]

null (parent of S)

Stop: reached source

[G, D, A, S]

—

Reverse the path

[S, A, D, G]

Memory Usage Analysis

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.

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 }

Parent Tracking for Path Reconstruction

Beyond Distance: Recovering the Path Itself

The Parent Array Concept

Augmenting BFS with Parent Tracking

Path Reconstruction Deep Dive

Handling Edge Cases

Memory Considerations

When Multiple Shortest Paths Exist

Practical Implementation Patterns

There’s more to understand.

Parent Tracking for Path Reconstruction

Beyond Distance: Recovering the Path Itself

The Parent Array Concept

Augmenting BFS with Parent Tracking

Path Reconstruction Deep Dive

Handling Edge Cases

Memory Considerations

When Multiple Shortest Paths Exist

Practical Implementation Patterns

There’s more to understand.