简单BFS讲解

广度优先搜索 ,英文 Breadth-First Search,简称 BFS
广度优先搜索类似深度优先搜索,也是非常实用的算法
它从指定节点开始,逐层访问所有邻近节点,直到找到目标或遍历完所有节点。
总体流程

  • 创建一个队列,把起点入队
  • 遍历队首能到达的所有选项,将其入队
  • 将队首元素出队
  • 重复第2、3条流程,直到找到结果

代码模板

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {};
const int dy[] = {};
//定义方向,和dfs一样 
int n, m;//地图的大小 
struct node{
	
	//定义队列要的信息 
};//由于队列要记录很多组信息,所以要一个结构体队列 
queue<node> q;
//定义一个结构体队列 
bool vis[][];
//标记走过的地方 
char mp[][];
//地图 
void bfs(){//定义函数(其实可以直接写进主函数) 
	q.push(node { , , , });//把起点信息入队  
	while(!q.empty()){//只要还有地方没有走,就继续  
		node now = q.front();//把队首存下来  
		q.pop();//把队首出队 
		for(int i = 0;i <  ;i++){//重复走这个点能够走到的节点 
			int nx = dx[i];
			int ny = dy[i];
			//看下一个到达的节点,同dfs 
			if(!vis[nx][ny] && nx > 0 && ny > 0 && nx <= n && ny <= m ……){//判断走这个点行不行 
				vis[nx][ny] = 1;//标记这个点走过 
				q.push(node { , , , });//将新的点入队
				if(……){//结束条件 
					cout << ;//输出结果 
					return;
				} 
			} 
		} 
	} 
} 
int main(){
	//输入
	bfs(); 
	return 0;
}

以上就是简单的bfs应用

4 个赞

好家伙,全文 \LaTeX

3 个赞

来这里更详细 所有种类搜索讲解 - 【活动】信奥笔记分享 / 提高组 - 信友队论坛

3 个赞

本蒟蒻第一次发这种 @金杭东

1 个赞

【搜索】搜索的讲解 我也有QaQ

3 个赞

这几天时间比较多,就来写这个了

1 个赞

最近在学网络流没时间写讲解。
学完写一篇网络流的

3 个赞

算法名请不要使用 LaTeX。

3 个赞

我写题解就这样过,惨遭打回

3 个赞

我也经历过这样的 qwq

2 个赞

打回?

1 个赞

e问一下可以借楼宣题解吗?

2 个赞

@冯俊骁 你没有写过洛谷题解吗?

2 个赞

真能宣,我知道你想宣啥

3 个赞

no
我只在洛谷打卡+刷题

1 个赞

等我学完网络流那题我也去看看

3 个赞

我只写过2篇

3 个赞

我也不多https://www.luogu.com.cn/user/1004142#article

3 个赞

一篇数学绿题,一篇小学生做的题)

2 个赞

能选十八,那我就宣一下: 题解:P2680 [NOIP 2015 提高组] 运输计划 - 洛谷专栏

1 个赞