使用 C++ 中的 BFS 查找从一个顶点到其余点的路径
c++server side programmingprogramming更新于 2025/3/15 10:52:17
在这个问题中，我们给出了一个以邻接表表示的有向图。 我们的任务是创建一个程序，使用 BFS 查找从一个顶点到其余顶点的路径。
BFS（广度优先搜索）是一种以广度运动遍历图形的算法，当任何迭代中出现死胡同时，使用队列记住获取下一个顶点以开始搜索。
让我们举一个例子来理解这个问题，
输入 −
输出
S
A <= S
B <= A <= S
C <= S
D <= C <= S
解决方法
为了解决这个问题，我们将对图中的每个元素执行 BFS 搜索算法。为了执行任务，我们将创建一个队列，该队列将存储对任何节点的访问标志。然后，使用访问过的数组，我们将检查元素是否被访问过（二进制值 0 和 1 表示访问）。
现在，我们将逐步解决该示例，以了解解决方案的工作原理，
从节点 S 开始，
我们将直接访问节点 A。
要到达节点 B，我们将首先访问节点 A，然后遍历节点 A 到达节点 B。
要到达节点 C，我们将直接从 S 访问 C。
要到达节点 D，我们将首先访问节点 C，然后然后是节点 D。
示例
程序用于说明我们的解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void printPath(vector<int> parent, int initial, int node){
while (initial != node){
cout<<node<<" <= ";
node = parent[node];
}
cout<<node<<endl;
}
void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){
vector<int> parent(graphSize, 0);
vector<int> queue(graphSize, 0);
int front = -1, rear = -1;
vector<int> isVisited(graphSize, 0);
isVisited[0] = 1;
parent[0] = initial;
queue[++rear] = initial;
int k;
while (front != rear)
{
k = queue[++front];
for (int j:graphAdjList[k]){
if (isVisited[j] == 0){
queue[++rear] = j;
isVisited[j] = 1;
parent[j] = k;
}
}
}
for (k = 0; k < graphSize; k++)
printPath(parent, initial, k);
}
int main(){
vector<vector<int> > graphAdjList;
graphAdjList.push_back({1, 3});
graphAdjList.push_back({0, 2});
graphAdjList.push_back({1});
graphAdjList.push_back({4});
graphAdjList.push_back({0});
int graphSize = graphAdjList.size();
int initial = 0;
cout<<"从顶点 '0' 到图中所有其他顶点的路径为 :\n";
findPathBFS(graphAdjList, initial,graphSize);
}
输出
从顶点 '0' 到图中所有其他顶点的路径为： 0 1 <= 0 2 <= 1 <= 0 3 <= 0 4 <= 3 <= 0
