如何使用BFS查找两个节点之间的距离？

Question

我使用维基百科的伪代码编写了以下c++ BFS代码。

该函数接受两个参数s和t。其中s是源节点，t是目标节点。如果找到目标节点，则返回目标本身，否则返回-1。

以下是我的代码：

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
    while(!Q.empty()){
        int t = Q.back();
        Q.pop_back();
            if(t == target){
                return t;
            }
            for(unsigned int i = 0;i < Graph[t].edges.size();i++){
                int u = Graph[t].edges[i];
                if(!Graph[u].visited){
                    Graph[u].visited = true;
                    Q.push_front(u);
                }
            }
    }
    return -1;
} 

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> k;
for(int i = 0;i < k; i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    Graph[a].edges.push_back(b);
    Graph[b].edges.push_back(a);
}

for(int i = 0;i < n; i++){
    Graph[i].visited = false;
}

int s,t;
cin >> s >> t;

cout << BFS(Graph,s,t);

  }

我在维基百科上看到这篇文章：

广度优先搜索可以用于解决图论中的许多问题，例如：
查找两个节点u和v之间的最短路径（路径长度由边数测量）

如何更改我的BFS函数以返回从s到t的最短路径，并在不存在路径时返回-1？

- 2147483647

---

创建一个变量来存储你与起始节点之间的距离。每次你进入到一个新的节点时，更新这个距离变量。 - jondinham

@PaulDinh 但这会给出最短的距离还是仅仅距离？ - 2147483647

就像你上面的实现一样，如果将一个距离变量放入其中，那么它只是行进时到当前节点的距离。 - jondinham

@PaulDinh，我按照你说的做了，但是每次到达新节点更新距离变量时，答案比实际答案要大得多。 - 2147483647

Answer 1

广度优先搜索是按照距离d从起始点开始访问所有节点，再访问任何距离d+1的节点。因此，当您以广度优先顺序遍历图形时，第一次遇到目标节点时，您已经以最短可能的路径到达那里。

Nathan S. 的答案是正确的，但我希望这个答案能够更好地解释为什么这样做有效。Paul Dinh的评论也是正确的；您可以很容易地修改Nathan的答案来跟踪距离而不是实际路径。

- Jamey Sharp

---

请问在代码的哪个具体位置应该增加计数器？ - 2147483647

那是一个棘手的部分，没错！当你从deque中弹出一个节点时，你会得到到该节点的距离。然后你推入deque的每个相邻节点都有其父节点的距离加1。 - Jamey Sharp

那我应该为每个顶点维护一个单独的变量来存储其与父节点之间的距离吗？ - 2147483647

是的，实现这个的直接方法需要与您访问的节点数量成比例的存储空间。但是，您应该考虑一些问题：1）您是否已经分配了可以添加此数据的结构？2）您是否想记住所有节点的这些距离，还是在找到目标后释放内存？ （这取决于您的应用程序。）3）您如何更改算法以仅使用一个变量来测量当前深度的最短距离？ - Jamey Sharp

Answer 2

当你生成一个新节点时，请记录生成该节点的父节点的ID。然后，当你到达目标时，只需向后追溯父节点，直到到达起始状态。例如，你可以将起点标记为其自己的父节点，这意味着它是起始状态。或者，只需使用预定义的值（-1）表示没有父节点。

因此，在你的代码中，不要标记状态为已访问，而是有一个父ID。父ID最初可以设置为-1，然后在更改时进行更新。父ID可以只是父节点在图结构中的位置。

- Nathan S.

Answer 3

如果想要了解BFS算法的良好实现和解释，请查看CXXGraph库源代码。

- Zig Razor

---

这应该是一条注释，而不是一个答案。 - Kennet Celeste

首先，你提供的链接中没有BFS算法的解释。其次，这并没有回答问题，第三，你是在宣传自己的GitHub吗？ - Cheejyg