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

Question

我使用维基百科的伪代码在C++中编写了BFS代码。 该函数需要两个参数s，t。其中s是源节点，t是目标，如果目标是fount，则搜索返回目标本身，否则返回-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); 

    } 

我在维基百科阅读：

广度优先搜索可用于解决图论中的许多问题，例如：
寻找之间的最短路径

如何更改我的功能BFS从回归的最短路径，以T和返回-1，如果没有路径存在（由>的边缘>数量来衡量与路径长度）两个节点u和v S'

Answer 1

当您生成新节点时，请跟踪生成节点的父节点的ID。然后，当您到达目标时，您只需向后追踪父母，直到您达到开始状态。例如，您可以将开始标记为其父项，这意味着它是开始状态。或者，只需使用预定义的值（-1）来表示没有父项。

因此，在您的代码中，不是将状态标记为已访问，而是具有父级ID。父ids最初可以设置为-1，然后在更改时更新。父ID可以只是父级图结构中的位置。

Answer 2

根据定义，广度优先搜索在距离起点处距离d处访问所有节点，然后访问距离为d+1的任何节点。因此，当您以广度优先的顺序遍历图时，第一次遇到目标节点时，您已经通过尽可能短的路线到达那里。

Nathan S.'答案是正确的，但我希望这个答案提供了一些关于为什么这个工作的更直觉。保罗丁的评论也是正确的;你可以修改内森的答案来追踪距离，而不是实际的路径。