我需要怎么做才能用这个BFS代码显示最短路径？

Question

我写了一个C++程序，用BFS算法找出最短路径。但是，我找不到打印出路径的方法，例如，打印出构成最短路径的节点。我应该添加什么东西，才能使我有可能打印出该路径？

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using st = set<ll>;
using kiwi = queue<ll>;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll mx=1e5+123;
bool visited[mx];
ll dist[mx];
int main(){
    fastio;
    ll node, edge;
    cin>>node>>edge;
    st adj[node+1];
    for(ll i=1;i<=edge;++i){
        ll node1, node2;
        cin>>node1>>node2;
        adj[node1].emplace(node2);
        adj[node2].emplace(node1);
    }
    ///BFS
    ll src, dest; cin>>src>>dest;
    kiwi q;
    visited[src]=true; dist[src]=0;
    q.push(src);
    while(!q.empty()){
        ll s=q.front(); q.pop();
        for(auto& x:adj[s]){
            if(visited[x]) continue;
            visited[x] = true;
            dist[x] = dist[s]+1;
            q.push(x);
        }
    }
    cout<<dist[dest]<<endl;
return 0;
}

Answer 1

从源点到目的地的最短路径可以通过跟踪每一个节点的父节点来找到，创建一个数组parent[node+1]，并将源点的父节点赋值为0。现在你可以通过访问目的节点的父节点和该节点的父节点来获取从目的节点到源节点的路径，以此类推，直到到达源节点(src的父节点为0)。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using st = set<ll>;
using kiwi = queue<ll>;
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll mx=1e5+123;
bool visited[mx];
ll dist[mx];
int main(){
    fastio;
    ll node, edge;
    cin>>node>>edge;
    st adj[node+1];
    for(ll i=1;i<=edge;++i){
        ll node1, node2;
        cin>>node1>>node2;
        adj[node1].emplace(node2);
        adj[node2].emplace(node1);
    }
    ///BFS
    ll src, dest; cin>>src>>dest;
    kiwi q;
    visited[src]=true; dist[src]=0;
    // Create parent array to keep track of parents
    int parent[node+1]={-1};
    q.push(src);
    // Assign parent of source as 0 since we dont need source's parent.
    parent[src]=0;
    while(!q.empty()){
        ll s=q.front(); q.pop();
        for(auto& x:adj[s]){
            if(visited[x]) continue;
            visited[x] = true;
            // The parent of x will be s
            parent[x]=s;
            dist[x] = dist[s]+1;
            q.push(x);
        }
    }
    cout<<"Shortest path distance : "<<dist[dest]<<endl;

    // Use stack to store path from dest to src
    stack<int> s;
    s.push(dest);
    cout<<"The Shortest path is : ";
    // Travers untill parent is 0, since we fixed parent  of src as 0.
    while(parent[dest]!=0)
    {
        s.push(parent[dest]);
        // Traverse from dest to its parent.
        dest=parent[dest];
    }
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
return 0;
}