C++ 广度优先搜索
问题引入
对于每一个问题，都会有相应的解，在之前的学习中求解的过程，都是以一条条线的形式产生可能解进行筛选验证是否正确。本章节我们来考虑另外一种思路，类似于洪水爆发，从一个源头开始逐渐蔓延开来，直到所有可达的区域都被洪水淹没，所以我们也把这种算法称之为洪泛法。洪泛法会以面的形式同步扩展更多的可行解，进而拓展广度。
单纯的文字描述无法很好的帮助同学们理解上面的说法，认真学完本章节的内容，相信同学们可以很好的理解广度优先搜索算法。
广度优先搜索算法
广度优先搜索（英文：Breadth-First Search，简称BFS）的思路是会优先考虑每种状态和初始状态的距离，也就是与初始状态越接近的情况就会优先考虑。再具体一点：每个时刻（阶段）要做的事情就是从上个时刻（阶段）每个状态扩展出新的状态。
广度优先搜索使用队列或数组模拟实现：先将初始状态加入到空的队列中，然后每次取出队首，找出队首所能扩展到的状态，再将其压入队列；如此反复，直到队列为空。这样就能保证一个状态在被访问时一定是采用的最短路径。
例如洪水从A点爆发（如下左图所示），在每个点都沿着上下左右的方向淹没相邻的点，那么最终整个地图淹没的时间如下右图所示。
把扩展的情况按层次划分，可以得到下图：
可以发现，广搜更适合解决从起始点到目标点的最短路问题。一般来说，题目描述的是求解最少多少步、最短距离、最短时间这种问题可以考虑用广搜求解。
广搜的模板：
本章节例题将以两种解法进行全面充分的学习广度优先搜索的实现方式，增强同学们的理解。
1. 队列(推荐写法)
2. 数组模拟队列(重点学习)
全局状态变量 void bfs(当前结点) { 当前结点入队 while (队列不为空) { 取出队首节点作为当前结点 if (当前节点是目标结点) 进行相应处理（输出当前解、更新最优解、退出返回等） for (由当前结点衍生新结点) { if (新结点没有访问过 && 需要访问) { 新结点入队 } } //队首结点已衍生完毕，没有用处了 队首结点出队 } } int main() { ...; bfs(初始结点); ...; }
广搜在搜索过程中形象化的运行过程：
例题
快乐的马里奥
-
分析
通读题意，不难发现本质上就是一个二维数组填数字，但是应该按照怎样的方式进行填写，才能达成题目所说的目标呢？？
同学们自己动手按照题意填一下上面3*4的方格。
以(1,1)作为初始结点(当前结点)，先后衍生两个结点(1,2)、(2,1)，按顺序填数，并按顺序成为当前结点再次衍生，依次往复处理填数，即可得到答案。
提供两种解法：
-
队列方法。以当前结点为队首，衍生出的结点按次序入队，把队首出队，依次往复，直到队列为空。
-
数组模拟队列。设置head和tail分别指向二维数组的头尾。以head指向的元素为当前结点，衍生出的结点按次序以tail指向存储，把head后移一位，依次往复，直到head>tail。
-
-
示例代码
解：
#include<bits/stdc++.h> using namespace std; bool b[105][105];//b[i][j]==0表示点(i,j)没有被标记过 int a[105][105]; int fx[4] = {0, 1, 0, -1}, //方向数组 fy[4] = {1, 0, -1, 0}; //行列值的增量 queue<int>p, q; //分别存点的行列标 int m, n, t = 0; void bfs(int x, int y) { p.push(x); q.push(y); t++; a[x][y] = t; //赋值 b[x][y] = 1; //标记为1 while (p.empty() != 1) { //当前还有待判断的点 int tx = p.front(); int ty = q.front(); //取队首位置(tx,ty) for (int i = 0; i <= 3; i++) { //以当前点为中心，向四个方向查找位置 int dx = tx + fx[i]; int dy = ty + fy[i]; //(dx,dy) if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && b[dx][dy] == 0) { //表示(dx,dy)不越界 // cout<<dx<<" "<<dy<<endl; p.push(dx);//入队 q.push(dy); t++; a[dx][dy] = t; //赋值 b[dx][dy] = 1; //标记，防止找重 } } p.pop(); q.pop(); } } int main() { cin >> n >> m; bfs(1, 1); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << endl; } }
泉水
-
分析
通读题意，很形象地表达了前文提到的洪泛法。从一个源头开始，逐渐蔓延开，直到所有的地方都被淹没。只需要在广搜过程中进行计数即可，但如何才能正确的表达淹没呢？？具体实现过程中还有一些细节，仔细研读示例代码。
-
示例代码
#include<bits/stdc++.h> using namespace std; int a[1005][1005]; int f[1005][1005]; //标记是否已被淹没 int n, m, p1, p2; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int cnt, T; queue<int> qx, qy; void bfs(int x, int y) { //初始结点入队 qx.push(x); qy.push(y); cnt++;//淹没区域+1 f[x][y] = 1; //标记 int tx, ty; while (qx.empty() == false) { for (int i = 0; i <= 3; i++) { tx = qx.front() + dx[i]; ty = qy.front() + dy[i]; if (a[tx][ty] <= T && f[tx][ty] == 0 && tx >= 1 && tx <= n && ty >= 1 && ty <= m) { //可行性 cnt++; f[tx][ty] = 1; //被淹没 qx.push(tx); qy.push(ty); } } qx.pop(); qy.pop(); } } int main() { cin >> n >> m >> p1 >> p2; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; T = a[p1][p2]; //记录泉眼的高度 小于等于T的都被淹没 bfs(p1, p2); cout << cnt; }
关系网络
-
分析
通读特意，非常抽象，需要通过题目样例，一个个的对照对应仔细的理解。行代表i号人，列代表认识的人，比如(3,5)位置的值是0，说明3号人不认识5号人。
题目需要求得最少的人数。用广搜求解，以x为初始结点，那么如何进行衍生结点呢？？需要通过二维数组的情况进行衍生结点。仔细研读代码，认真学习。
-
示例代码
#include<bits/stdc++.h> using namespace std; int a[105][105]; int f[105];//标记 同时也是记录通过的人数 //f[10]=5 x认识10号需要通过5个人 包括x和10的计数结果 int n, x, y; queue<int> qx; void bfs(int x) { qx.push(x); f[x] = 1; //标记 但是有细节，要思考 while (qx.empty() == false) { for (int j = 1; j <= n; j++) { //通过循环查看 qx.front()行j列的值进行衍生 if (a[qx.front()][j] == 1 && f[j] == 0) { //认识j号 而且j号之前不认识 f[j] = f[qx.front()] + 1; qx.push(j); } } //队头认识的人已经穷尽 qx.pop(); } } int main() { cin >> n >> x >> y; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j]; bfs(x); cout << f[y] - 2; //为什么减2？ return 0; }