Discrete Mathsfor Engineers

6. BFS Tree & Path Reconstruction

BFS does more than compute distances. It produces a predecessor relation π that encodes a BFS tree rooted at the source.

In this part, we make that output explicit and show how to reconstruct a shortest path from s to any reachable vertex v.

6.1 What BFS Produces

After running BFS from a source s, each vertex v has:

• d[v] — shortest-path distance from s to v (in edges)
• π[v] — predecessor of v on a shortest path (or NIL)

6.2 The Predecessor Subgraph

Define the predecessor edge set:

The graph T = (V, E_π) is called the BFS predecessor subgraph.

6.3 Why This Is a Tree

Two facts give the tree structure:

1. Unique parent: Every reachable vertex v ≠ s gets exactly one predecessor π[v].
2. Acyclic: Distances strictly decrease when following predecessors: d[π[v]] = d[v] − 1. So you can never come back to a vertex with the same distance.

6.4 Small Formal Diagram

The predecessor pointers connect consecutive layers:

L0:   s
      |
L1:  a   b
     |   |
L2:  c   d   e
         |
L3:      f

Edges are (π[v], v).
Each edge goes from layer k to layer k+1.

This is why the predecessor subgraph is both a tree and a shortest-path structure.

6.5 Path Reconstruction (Definition)

A reconstructed path from s to a reachable vertex v is:

The length is k = d[v].

6.6 CLRS-Style Procedure — PRINT-PATH

CLRS presents reconstruction as a recursive procedure on predecessors:

PRINT-PATH(π, s, v):

    if v == s:
        print s
    else if π[v] == NIL:
        print "no path"
    else:
        PRINT-PATH(π, s, π[v])
        print v

6.7 Iterative Reconstruction (Engineering-Friendly)

In practice, you often build the path in reverse, then reverse it:

RECONSTRUCT-PATH(π, s, v):

    path = []
    cur = v

    while cur != NIL:
        path.append(cur)
        if cur == s:
            break
        cur = π[cur]

    if path.last != s:
        return []   // no path

    reverse(path)
    return path

6.8 Worked Example

Suppose BFS from s produced:

Reconstructing the path to f follows predecessors:

Reversing gives the shortest path:

6.9 Engineering Patterns

The BFS tree and predecessor pointers show up everywhere:

• Routing / shortest hops: reconstruct the hop-by-hop path in networks
• Breadcrumbs: parent pointers from a node up to a root (UI navigation)
• Org charts / hierarchies: store parent pointers to rebuild chains
• Dependency exploration: discover layers of impact from a starting component