目录

简介

层序遍历

例题

献给阿尔吉侬的花束

全球变暖

---

简介

🍦宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，之前我们在实现对树的层序遍历时就使用过它。不仅如此它还在求最短路径，找连通块时具有奇效。

🍦层序遍历基本上借助于队列，将队头向各个方向展开，使相与其相关联的数据入队，再进行访问，现在不妨我们先回顾一下层序遍历的基本操作吧。

层序遍历

🍦传送门：二叉树的层序遍历

 🍦我们通过借助队列将一开始的根节点逐渐展开，凭借队列先进先出的原则，会根据展开的顺序进行访问，由此根据题目的规则我们要将每层的数据分别存储在一个 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 存他的两个下标。

#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的入门讲解到这里就结束了，如果这篇文章对你有用的话还请留下你的三连加关注。