BFS Path Reconstruction

Concept

BFS finds the shortest path in an unweighted graph. To reconstruct the actual path (not just the distance), we store a parent array during BFS. After BFS completes, we trace back from the target to the source using the parent pointers.

When to Use

  • ▸Finding the shortest path AND printing the actual route
  • ▸Problems that ask 'print the path from A to B'
  • ▸Message routing, navigation, or any problem needing the sequence of nodes

Intuition

During BFS, when we discover a new node, we remember who discovered it (its parent). Once we reach the target, we follow parent pointers backwards: target -> parent -> parent -> ... -> source. Since BFS guarantees shortest distance, this chain gives us the shortest path. We use a stack to reverse the order for printing.

Complexity

Time
O(V + E)
Space
O(V)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n+1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> dist(n+1, -1);
    vector<int> pa(n+1, -1);
    queue<int> q;

    dist[1] = 1;
    q.push(1);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(int v : adj[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                pa[v] = u;
                q.push(v);
            }
        }
    }

    if(dist[n] == -1){
        cout << "IMPOSSIBLE";
    }
    else{
        stack<int> path;

        cout << dist[n] << "\n";

        int cur = n;
        while(cur != -1){
            path.push(cur);
            cur = pa[cur];
        }

        while(!path.empty()){
            cout << path.top() << " ";
            path.pop();
        }
    }

    return 0;
}

// Sample Input:
// 5 5
// 1 2
// 1 3
// 2 4
// 3 4
// 4 5
//
// Sample Output:
// 3
// 1 2 4 5