我需要做什么才能使用此 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] 并将源的父级指定为零。在从源更新父数组执行 bfs 时。现在，您可以通过访问目标的父节点和该节点的父节点等来获取从目标到源的路径，直到到达源（源的父节点为 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;
}

我需要做什么才能使用此 BFS 代码显示最短路径？

What do I need to do to display the shortest path using this BFS code?

c++

breadth-first-search

shortest-path