目录
简介
层序遍历
例题
献给阿尔吉侬的花束
全球变暖
简介
🍦宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，之前我们在实现对树的层序遍历时就使用过它。不仅如此它还在求最短路径，找连通块时具有奇效。
🍦层序遍历基本上借助于队列，将队头向各个方向展开，使相与其相关联的数据入队，再进行访问，现在不妨我们先回顾一下层序遍历的基本操作吧。
层序遍历
🍦传送门：二叉树的层序遍历
🍦我们通过借助队列将一开始的根节点逐渐展开，凭借队列先进先出的原则，会根据展开的顺序进行访问，由此根据题目的规则我们要将每层的数据分别存储在一个 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;
}
};例题
献给阿尔吉侬的花束
🍦传送门：AcWing 1101. 献给阿尔吉侬的花束
🍦根据题目所说，有一只小老鼠，从起点要去到终点，每步只能选上下左右走一步且不能穿越障碍物，要我们求从起点到终点的最短步数。 这就是典型使用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 存他的两个下标。文章来源：https://www.toymoban.com/news/detail-406056.html
#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的入门讲解到这里就结束了，如果这篇文章对你有用的话还请留下你的三连加关注。文章来源地址https://www.toymoban.com/news/detail-406056.html
到了这里，关于【算法】手把手学会BFS的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
