前言
唤我沈七就好。
往期专栏：
因为BFS需要靠队列来实现，所以在阅读下面的文章时，需要用先了解一下什么是队列。
可以看我之前对队列的讲解。
基本概念
BFS：是 Breadth-First-Search 简称，即广度优先搜索算法。
与 DFS 一样也是一种用于遍历或搜索树或图的算法。不同的是，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。而 DFS 是沿着树的深度遍历树的节点。
BFS 也被称为层序遍历，即一层一层的遍历，这样效率就高的多，所以相对于 DFS 指数级枚举，BFS 明显是更快的。
因为要同时遍历每一层的结点，所以我们要借助队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。而从队列中取出的顺序即为层序遍历的顺序。
算法思想
BFS 遍历有一个很重要的特点就是，第一个到达目标节点一定是最短路径。
如下图，因为BFS是一层一层的遍历且每一层距离根节点的距离都相同，遍历顺序由内而外，故BFS每到达一个目标节点一定是最短路径。
所以根据这一个特性 BFS 可以解决最短问题。
必备概念
1. STL queue
我一般写BFS喜欢用 STL 的现成实现好的队列 queue。
当然你也可以用数组模拟实现队列。如果想了解如果用数组模拟队列，可以看我这篇文章。
接下来我简单的介绍一下 STL queue 的使用方法。
queue<pair<int,int>> q; q.front() 返回队头元素 q.push() 将元素入队 q.pop() 弹出队头元素
这里我定义的队列类型是 pair ，这是一个二元组，其实简单说这就是一个只有两个变量的结构体。
只不过直接用 pair 来定义方便一些。
定义成二元组，是为了方便表示坐标 （ x , y ）。
初次以外还有一些常用的小优化
#define x first #define y second typedef pair<int,int>PII; queue<PII> q;
这样做的目的完全是为了简化代码。
typedef可以重新定义 数据结构 的名称，改成 PII 的单纯是为了简化代码。
fist和second是pair二元组第一和第二个元素，分别通过宏定义用 x 和 y 代替 也是为了简化代码
2 . 偏移量数组
int pos[4][2]={-1,0,0,1,1,0,0,-1}; 扩展方法：偏移量数组
这是一个扩展某一个坐标周围的点的绝佳利器。
详细介绍我在我第一篇博客里有详细介绍，有兴趣的同学可以看看。
常用模板
伪代码模板
void BFS () { ① 初始化队列 ② 将起点入队 ③ 标记起点已经被访问 ④ while（ 队列不空时 ） { ⑤ 取出队首元素 u ，存放到 t 变量里 ，u 元素出队 ⑥ 扩展 t 结点 { ⑦ 判重新节点 ⑧ 如果未被访问，且满足要求，记录当前点到起点的距离 ⑨ 标记扩展的新结点 ⑩ 将扩展的新节点入队 } } }
C++ 模板
#define x first #define y second typedef pair<int,int>PII; queue<PII> q; STL 的队列，适用的是一个二元组，方便表示坐标。 q.push(start) ; 初始状态入队 while（！q.empty()) 当队列不空的时候。 PII t=q.front(); q.pop(); 取出队头元素，放到 t 里面去 int pos[4][2]={-1,0,0,1,1,0,0,-1}; 扩展方法：偏移量数组 for(int i=0;i<4;i++) 扩展t结点 { int tx=t.x+pos[i][0]; int ty=t.y+pos[i][1]; if(g[tx][ty]=='#')continue; 判重新节点 if(g[tx][ty]=='.') { dis[tx][ty]=dis[t.x][t.y]+1; 记录当前点到起点的距离； g[tx][ty]='#'; 标记好已经走过路 q.push({tx,ty}); 确定是新节点后入队 } }
或许读者到现在也是懵懵懂懂，笔者能力有限，没办法把为什么这样做讲解的通俗易懂，如果实在想搞明白原理的话，可以去 AcWing 算法基础课中一探究竟。
而在我看来，只要牢记模板，做出题来也不是问题。
下面我就讲解一下能用BFS解决的经典的走迷宫的问题
经典例题：走迷宫
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
有一个人位于左上角 ( 1 , 1 )处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角 ( n , m ) 处，至少需要移动多少次。
分析：提炼题目大意，此题就是求解从迷宫的左上角到迷宫的右下角，在不碰到障碍的最短路径是多少。因为是最短路径问题， 故用 BFS 解决相对容易。
详细的解释都在代码里~
#include<bits/stdc++.h> using namespace std; #define x first #define y second int n,m; typedef pair<int,int>PII; int a[110][110]; 储存地图 int dis[110][110]; 储存距离 int pos[4][2]={-1,0,0,1,1,0,0,-1}; 偏移量数组 void bfs(PII start) { queue<PII>q; q.push(start); 初始状态入队 while(!q.empty()) 队列不空时 { PII t=q.front(); 取出队首元素，存放到 t 变量里 ，元素出队 q.pop(); 元素出队 for (int i = 0; i < 4; i ++ ) 扩展 t 结点 { int tx=t.x+pos[i][0],ty=t.y+pos[i][1]; if(a[tx][ty]==-1||a[tx][ty]==1)continue; 判断是否越界或者碰到障碍 if(a[tx][ty]==0) 如果未被访问， { dis[tx][ty]=dis[t.x][t.y]+1; 记录当前点到起点的距离 a[tx][ty]=-1; 标记扩展的新结点被访问 q.push({tx,ty}); 将扩展的新节点入队 } if(tx==n&&ty==m) 如果到达右下角 { cout<<dis[tx][ty]; 返回右下角到起点的距离 return; } } } } int main() { cin>>n>>m; memset(a, -1, sizeof a); 初始化为 -1 ，这样方便 判断边界 for (int i = 1; i <= n; i ++ ) 从1开始读入地图方便判断边界，这样地图都会被初始化的 -1 包围 for (int j = 1; j <= m; j ++ ) 这样判断扩展的点是否越界时，只要判断是不是 -1 即可 { cin>>a[i][j]; } PII start; 定义一个二元组，储存起点，传入到BFS函数里 start.x=1,start.y=1; bfs(start); return 0; }
完结散花
ok以上就是对 暴力搜索之BFS 的全部讲解啦，很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
题目练习
检验知识是否学会当然是不断刷题啦，下面我给出一部分DFS相关的一些经典题目。
后续如果我有时间就更新这部分知识的题解，到时候就可以配套学习啦。
参考文章
参考文献
https://www.acwing.com/activity/content/19/
