目录
简介
🍦宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，之前我们在实现对树的层序遍历时就使用过它。不仅如此它还在求最短路径，找连通块时具有奇效。
🍦层序遍历基本上借助于队列，将队头向各个方向展开，使相与其相关联的数据入队，再进行访问，现在不妨我们先回顾一下层序遍历的基本操作吧。
层序遍历
🍦传送门：二叉树的层序遍历
编辑
🍦我们通过借助队列将一开始的根节点逐渐展开，凭借队列先进先出的原则，会根据展开的顺序进行访问，由此根据题目的规则我们要将每层的数据分别存储在一个 vector 中，因此需要每次计算好各层结点的数量。
🍦若我们确保每次队头的数据就是这层的第一个结点，那么我们便能保证此时队列的数据量就是这层的结点数。所以我们需要两层循环，第一层代表层的循环，而第二层代表该层结点的循环。
编辑
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; //要返回的vector if(!root) return ret; //如果树为空则返回空的数组 queue<TreeNode*> q; //定义队列 q.push(root); //根节点入队 while(q.size()) //只要队列里还有值则表示还没有走完 { int len = q.size(); //当前队列里的数量就是该层的结点数 vector<int> v; for(int i = 0;i<len;i++) //循环层内的结点 { TreeNode* t = q.front(); //取队头 q.pop(); if(t->left) q.push(t->left); //展开左右孩子 if(t->right) q.push(t->right); v.push_back(t->val); //将自己的值插入vector } ret.push_back(v); } return ret; } };
例题
献给阿尔吉侬的花束
编辑
🍦根据题目所说，有一只小老鼠，从起点要去到终点，每步只能选上下左右走一步且不能穿越障碍物，要我们求从起点到终点的最短步数。 这就是典型使用bfs的经典场景。我们可以使用 bfs 遍历小鼠可能到达的位置，而当第一次到达终点时用的便是最短的步数。
🍦并且每次需要记录这个点是否走过，若走过便不重复走。这样也可以保证每个点的值都是最短的步数。第一次到终点就可以直接返回，若遍历不到终点则说明终点无法到达。而由于地图是一个二维的数组所以队列中存的值便是两个下标。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define x first #define y second typedef pair<int, int> PII; //使用pair存点的两个下标 const int N = 210; int n, m; char g[N][N]; //原地图 int dist[N][N]; //存最短的步数，没走过就存-1 int bfs(PII start, PII end) { queue<PII> q; //初始化队列 memset(dist, -1, sizeof dist); //所有值初始化成-1 dist[start.x][start.y] = 0; //起点到起点的距离为0 q.push(start); //起点入队 int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; //偏移量 while (q.size()) { auto t = q.front(); //取队头 q.pop(); for (int i = 0; i < 4; i++) { int x = t.x + dx[i], y = t.y + dy[i]; //根据偏移量移动 if (x < 0 || x >= n || y < 0 || y >= m) continue; // 出界 if (g[x][y] == '#') continue; // 障碍物 if (dist[x][y] != -1) continue; // 之前已经遍历过 dist[x][y] = dist[t.x][t.y] + 1; //没走过就往这走一步 if (end == make_pair(x, y)) return dist[x][y]; //走到终点就返回 q.push({ x, y }); //走到该点后入队 } } return -1; //遍历过还没找到终点则说明走不到终点 } int main() { int T; scanf("%d", &T); while (T--) //T组数据 { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%s", g[i]); PII start, end; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (g[i][j] == 'S') start = { i, j }; //找起点终点 else if (g[i][j] == 'E') end = { i, j }; int distance = bfs(start, end); //接收bfs的返回值 if (distance == -1) puts("oop!"); else printf("%d\n", distance); } return 0; }
全球变暖
🍦传送门：AcWing 1233. 全球变暖
编辑
🍦题目给我们一片海域，海域中有几座小岛，随着几年过后海平面上升，只要上下左右一边靠海的陆地就会被淹没，题目需要我们计算会被淹没的岛屿有多少个？
我们不妨思考一下，什么样的岛屿会被淹没？
编辑
🍦是的，如果一个岛屿的所有陆地都与海有接触就会被淹没，换过来只要一个岛屿至少有一个陆地没有跟海接触就不会被淹没。
🍦这时候，我们还可以发挥 bfs 解决连通块问题的能力，通过一块陆地便可以找到整个岛屿，之后再给岛屿做上标记表示这个岛已经判断过了，避免重复判断。最后找到所有的岛屿，便能够判断其是否会被淹没。同时，该题一样也是二维的 bfs 因此需要用 pair 存他的两个下标。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define x first #define y second using namespace std; typedef pair<int, int> PII; //使用pair存两个下标 const int N = 1010; char s[N][N]; //原地图 int n; bool st[N][N]; //记录这个点是否走过 int cnt = 0; //记录淹没的岛屿数 void bfs(PII begin) { queue<PII> q; //定义队列 q.push(begin); //起点入队 st[begin.x][begin.y] = true; //标记走过了 bool flag = true; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; while (q.size()) { auto t = q.front(); bool is_bound = false; //循环结束若还是false则说明没于海接触 for (int i = 0; i < 4; i++) { int x = dx[i] + t.x; int y = dy[i] + t.y; if (x < 0 || x >= n || y < 0 || y >= n) continue; //出界 if (s[x][y] == '.') //为海不走 { is_bound = true; continue; } if (st[x][y]) continue; //已经走过了 st[x][y] = true; //标记走过了 PII p = { x,y }; q.push(p); //延申路径 } if (!is_bound) //判断是否会被淹没 { flag = false; } q.pop(); //出队 } if (flag) //如果会被淹没cnt加一 { cnt++; } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%s", &s[i]); PII begin; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s[i][j] == '#') //找到陆地延申找这个岛屿 { if (!st[i][j]) //避免重复找 { begin = { i,j }; bfs(begin); } } } } printf("%d\n", cnt); return 0; }
🍦好了这次BFS的入门讲解到这里就结束了，如果这篇文章对你有用的话还请留下你的三连加关注。
