c++算法之BFS

BFS,广度优先搜索,和DFS一样,也是用来遍历树(或图)的算法。如下面的树:

广度优先搜索的遍历过程是这样的:

1.将根节点放入队列中

2.从队列中取出第一个元素,将队列中的第一个元素弹出

3.将所取得元素的全部节点加入队列中

4.判断队列是否为空

     a. 若是,则结束

     b.若不是,则跳到第二步

伪代码:

(1)初始化队列Q;visited[n]=0;
       (2)访问顶点v;visited[v]=1;顶点v入队列Q;
        (3) while(队列Q非空)   
                 v=队列Q的对头元素出队;
                 w=顶点v的第一个邻接点;
                 while(w存在) 
                     如果w未访问,则访问顶点w;
                     visited[w]=1;
                     顶点w入队列Q;
                     w=顶点v的下一个邻接点。

下面对这个树进行广搜(图很简陋,毕竟是手绘,请见谅):


代码如下:

#include<bits/stdc++.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() {
	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;
}

声明:以后到7月都不会更新了,毕竟学业繁忙。。。

谢谢对我的理解。

Alex172

  蔡徐坤打篮球是怎么回事呢?蔡徐坤相信大家都很熟悉,但是蔡徐坤打篮球是怎么回事呢,下面就让小编带大家一起了解吧。   蔡徐坤打篮球,其实就是蔡徐坤打篮球,大家可能会很惊讶蔡徐坤怎么会打篮球呢?但事实就是这样,小编也感到非常惊讶。   这就是关于蔡徐坤打篮球的事情了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!

相关推荐

1 条评论

Leave a Reply

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

c++算法之BFS
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close