C++实现BFS(广度优先搜索算法)
程序员文章站
2022-06-12 09:14:27
...
在上一篇文章中,笔者介绍了DFS,这篇文章介绍的是图论的另一个经典算法--BFS。
这一篇文章将对BFS作出介绍。队列的push操作将元素添加到队列的末尾,但pop操作将队列的第一个元素弹出,这与堆栈有差异。
我们构造这样一个图(如图1),并通过C++实现BFS
算法过程:
1.将根节点放入队列中
2.从队列中取出第一个元素,将队列中的第一个元素弹出
3.将所取得元素的全部节点加入队列中
4.判断队列是否为空
a. 若是,则结束
b.若不是,则跳到第二步
以下代码在vs2017中通过编译
//利用C++实现广度优先搜索算法,如有疑问请联系
//作者:cclplus 邮箱:aaa@qq.com
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
vector<vector<int>> tree;//声明一个二维向量
int flag[10];//用于搜索到了节点i的第几个节点
queue<int> M;//声明一个队列
int ar_tree[8] = { 1,1,1,3,5,3,5,7 };
void BFS(int node) {
int temp;
cout << node << " ";
//从队列中取出第一个节点
int m_first = M.front();
M.pop();
while(flag[node] < tree[node].size()) {
temp = tree[node][flag[node]];
flag[node]++;
//把temp加入队列中
M.push(temp);
}
if (!M.empty()) {
BFS(M.front());
}
}
int main() {
ios::sync_with_stdio(false);
memset(flag, 0, sizeof(flag));
int i,temp;
tree.resize(10);//图中的数共有九个节点
//生成树
for (i = 2; i <=9; i++) {
temp = ar_tree[i - 2];
tree[temp].push_back(i);//表示第i个节点为第temp个节点的子节点
}
//BFS
cout << "BFS过程:" << endl;
M.push(1);
BFS(1);
cout << endl;
return 0;
}
运行结果: