我使用维基百科的伪代码用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？
广度优先搜索，根据定义，在访问距离d+1的任何节点之前，先访问距离起点d的所有节点。因此，当你以广度优先的顺序遍历图时，当你第一次遇到目标节点时，你已经通过尽可能短的路线到达了那里。
Nathan S.的答案是正确的，尽管我希望这个答案能提供更多关于为什么这样做的直觉。Paul Dinh的评论也是正确的；你可以修改Nathan的答案来追踪距离，而不是实际的路径。
生成新节点时，请跟踪生成节点的父节点的id。然后，当你达到目标时，你只需要追溯父母，直到你达到开始状态。例如，您可以将开始标记为自己的父级，这意味着它是开始状态。或者，只需使用预定义的值(-1)来表示没有父级。
因此，在代码中，不要将状态标记为已访问，而是要有一个父id。父id最初可以设置为-1，然后在更改时更新。父id可以只是父的图形结构中的位置。
为了更好地实现和解释BFS算法，请检查此(CXXGraph)库源代码。