广度优先搜索：你是唯一

作者: Arabid | 来源:发表于2024-12-06 10:28 被阅读0次

LeetCode广度、深度优先搜索
搜索
算法与数据结构之搜索算法
图的遍历
深度优先搜索和广度优先搜索
深度优先广度优先
广度优先搜索算法
python 广度优先算法
广度优先搜索算法（go）
广度优先搜索算法(BFS)

阅读之前

请确认您了解队列的相关性质。

快速入门

前文，我们介绍了深度优先搜索（DFS）算法，这是一种“不撞南墙不回头”的算法，比如在下面这棵树中，DFS想找到标记着“6”的节点：

深搜
首先，DFS从节点1开始出发，先走到节点2，之后继续线下走到节点4。这时DFS就撞上了“南墙”，也是就到了layer > n的情况，此时DFS开始回溯到2，由于没有别的路径可走，DFS继续回到1。此时vis数组中2和4被标记为true，DFS接着走到3，之后先走到5，又撞上了墙，再次回溯到3，此时vis数组中的和5也被标记为true，DFS只能继续向6走，最终得到了答案。

但这样搜索是很慢的，比如我们前文提到的“过河卒”问题，虽然深搜的方法解决可行，但是数据量增大必然会导致超时的情况。在树中找节点的问题相比过河卒问题而言，最大的不同就是过河卒问题要求找出所有可行的道路，而我们的问题只要求找出一条最短的路径。那么我们为什么还要慢慢回溯呢？直接一层一层搜下去多好：

广搜
恭喜你，你发明了广度优先搜索（BFS）算法。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，进行彻底地搜索，直到找到结果为止。

深搜和广搜构成了基本搜索算法。字面意思，深度优先搜索以深度为主要以据，从浅到深的进行回溯式搜索，可以找到所有答案；广度优先搜索以广度（宽度）为主要依据，一层一层的进行地毯式搜索，可以找到最佳答案。

对比图

那么，如何进行广度优先搜索呢？我们知道，广搜中遍历顺序为先浅后深，以上图为例，BFS先遍历节点2之后遍历节点3，而不是节点4。也就是说，访问节点2之后，应该访问的是它的邻居，而不是它的下一级。如何实现这种看起来有些“跳跃”的访问呢？这时我们就要用到队列了。队列是一种尾进头出的FIFO（先入先出）线性表。考虑长度为3的队列 $Q$ 。

建立队列
队列经常进行如下两种操作：

push/emplace 入队：将元素插入队列的尾部。
入队操作
pop 出队：将元素从队列的头部弹出，此时 $a_1$ 成为队首元素。
出队操作
front 队首：字段，保存（不弹出）队列的头部元素。
队首字段
那么实现广搜的思路就明确了，还是以上图为例，我们建立一个不定长队列，从节点1出发，首先分别遇到节点2和3，并将它们压入队列。之后从队列头部——节点2出发，并弹出节点2，此时队列头部为节点3。从节点2出发会遇到节点4，压入队列。然后再次获取队头，为节点3，那么便可以弹出节点3并从节点3出发，遇到节点5和6，压入队列。此时队列里面就是4 5 6，再依次遍历即可。使用队列可以实现依次对邻居节点的访问。那么广度优先搜索便可以写为以下的基本模板：

建队及压首。建立不定长队列，并将要访问的所有内容的父元素压入队列。

queue<int> record;
record.emplace(x, y);

遍历队列。遍历队列的每一个元素。

while (!record.empty())

产生情况。取出队首的元素，检查其是否符合边界和其他条件。如果符合，通过遍历产生其所有子元素。

auto head = record.front();
record.pop();
if (head.layer <= n)
{
    node_left = head.left;
    node_right = head.right;
}

向下搜索。将该元素的所有子元素压入队列。

record.emplace(node_left);
record.emplace(node_right);

这样我们便实现了一个基本的深度优先搜索。

连通问题

在介绍DFS时，我们提到过连通问题，下面让我们看一个基本的连通性问题。

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M$ 的网格图表示。其中数据范围 $1\leq N\leq 100, 1\leq M\leq 100$ 。每个网格中有水（W）或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。输入第 $1$ 行：两个空格隔开的整数： $N$ 和 $M$ 。第 $2$ 行到第 $N+1$ 行：每行 $M$ 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。输出1行，表示水坑的数量。

解决这个问题，我们的思路就是找到所有连通的区域（即为水坑）为避免重复计数，我们可以从头开始寻找所有格子，一旦寻找到W，就遍历搜索整个W的连通区域，并将其中所有格子赋值为.，之后将结果累加1。显然这个问题可以通过DFS解决，但效率较低。

#include <iostream>

using namespace std;
int N, M, vis[101][101], ans = 0;
char grid[101][101];

void dfs(int x, int y);

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> grid[i][j];


    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (grid[i][j] == 'W')
            {
                dfs(i, j);
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

void dfs(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= M || grid[x][y] == '.' || vis[x][y])
        return;

    int dy[] = { 1,1,0,-1,-1,-1,0,1 };
    int dx[] = { 0,-1,-1,-1,0,1,1,1 };

    for (int i = 0; i < 8; ++i)
    {
        vis[x][y] = true;

        grid[x][y] = '.';
        int cx = x + dx[i];
        int cy = y + dy[i];

        dfs(cx, cy);

        vis[x][y] = false;
    }

}

现在考虑如何使用BFS解决这个问题，思路同上。

建队及压首。建立不定长队列，并将传入的坐标 $(i,j)$ 压入队列。

void bfs(int x, int y)
{
    queue<pair<int, int>> record;
    record.emplace(x, y);
}

遍历队列。遍历队列中存在的每一个坐标。

while (!record.empty())

产生情况。取出队首的坐标，检查其是否符合边界条件。如果符合，分别向八个方向遍历，产生其所有可以通到的坐标。

if (x >= N || y >= M || x < 0 || y < 0)
    continue;

if (grid[head.first][head.second] == 'W')
{
    grid[head.first][head.second] = '.';

    int dy[] = { 1,1,0,-1,-1,-1,0,1 };
    int dx[] = { 0,-1,-1,-1,0,1,1,1 };
}

向下搜索。将产生的所有坐标压入队列。

for (int c = 0; c < 8; ++c)
    record.emplace(head.first + dx[c], head.second + dy[c]);

完整广搜设计如下：

#include <iostream>
#include <queue>

using namespace std;
int N, M, ans = 0;
char grid[101][101];

void bfs(int x, int y);

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> grid[i][j];

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (grid[i][j] == 'W')
            {
                bfs(i, j);
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

void bfs(int x, int y)
{
    queue<pair<int, int>> record;
    record.emplace(x, y);

    while (!record.empty())
    {
        auto head = record.front();
        record.pop();

        if (x >= N || y >= M || x < 0 || y < 0)
            continue;

        if (grid[head.first][head.second] == 'W')
        {
            grid[head.first][head.second] = '.';

            int dy[] = { 1,1,0,-1,-1,-1,0,1 };
            int dx[] = { 0,-1,-1,-1,0,1,1,1 };

            for (int c = 0; c < 8; ++c)
                record.emplace(head.first + dx[c], head.second + dy[c]);
        }
    }
}

提交评测，发现在10个小样例的测试下，发现执行时间快了 $9.1\%$ ，运行内存减少了 $180％$ 。这说明广搜可以避免繁复的回溯搜索，很多场景下（尤其是求最短路径）性能明显优于深搜。

状态问题

广度优先搜索不仅可以解决在坐标系中的路径问题，也可以用于解决一系列状态问题。考虑一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（ $1 < i < N$ ）上有一个数字 $K_i$ （ $0 < K_i < N$ ）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3, 1, 2, 5$ 代表了 $K_i$ （ $K_1=3$ ， $K_2=3$ ，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？输入2行数据，第1行为三个用空格隔开的正整数，表示 $N, A, B$ （ $1 < N < 200$ ， $1 < A, B < N$ ）。第2行为 $N$ 个用空格隔开的非负整数，表示 $K_i$ 。输出1行，即最少按键次数，若无法到达，则输出 -1。

简单分析题目，我们可以发现电梯向上和向下可以看作两种状态，我们以这两种状态为前一种状态的产生情况为依据进行广搜。也就是说，我们每一次都分别将向上和向下两种情况添加到队列里继续搜索。需要特别注意的是，本题中可能出现“无法到达”的情况，即两次到达同一楼层，在这种况下，我们不应该重复访问同一楼层，楼层结构体设计如下：

struct floor
{
    int delta;
    int step;
    int now_layer;

    floor(int d = -1,int s = -1,int now = -1)
    {
        this->delta = d;
        this->step = s;
        this->now_layer = now;
    }

}layer[201];

下面开始构建BFS。

建队及压首。建立不定长队列，并将起始楼层压入队列。

int bfs(int f,int e)
{
    req.emplace(layer[f].delta, 0, f);
}

遍历队列。遍历队列中存在的每一个楼层。

while (!req.empty())

产生情况。取出目前的楼层，分别产生向上与向下的情况。注意：若两次到达同一楼层，则不应访问该该楼层，我们写在限制条件中。

auto now_up = head.now_layer + head.delta;
auto now_low = head.now_layer - head.delta;

向下搜索。将产生的所有楼层压入队列。

if (now_up <= N && !vis[now_up])
{
    vis[now_up] = true;
    req.emplace(layer[now_up].delta, head.step + 1, now_up);
}

if (now_low > 0 && !vis[now_low])
{
    vis[now_low] = true;
    req.emplace(layer[now_low].delta, head.step + 1, now_low);
}

这样便完成了BFS过程。

#include <iostream>
#include <queue>

using namespace std;

struct floor
{
    int delta;
    int step;
    int now_layer;

    floor(int d = -1,int s = -1,int now = -1)
    {
        this->delta = d;
        this->step = s;
        this->now_layer = now;
    }

}layer[201];

long long N, start, endlay, ans;
queue<struct floor> req;
bool vis[201];
int bfs(int f, int e);

int main()
{
    cin >> N >> start >> endlay;
    for (int i = 0; i < N; ++i)
    {
        cin >> layer[i + 1].delta;
    }

    cout << bfs(start, endlay);
    return 0;
}

int bfs(int f,int e)
{
    req.emplace(layer[f].delta, 0, f);

    while (!req.empty())
    {
        auto head = req.front();

        if (head.now_layer == endlay)
            return head.step;
        req.pop();
        
        auto now_up= head.now_layer + head.delta;
        auto now_low = head.now_layer - head.delta;

        if (now_up <= N && !vis[now_up]) 
        {
            vis[now_up] = true;
            req.emplace(layer[now_up].delta, head.step + 1, now_up);
        }

        if (now_low > 0 && !vis[now_low])
        {
            vis[now_low] = true;
            req.emplace(layer[now_low].delta, head.step + 1, now_low);
        }
    }
    return -1;
}

状态管理

很多时候，我们在进行BFS时要关注到许多不同的量，并不只是坐标平面上的一个坐标，或容易被分离出来的状态。

贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。根据预报，一共有 $M$ 颗流星 $(1\leq M\leq 50,000)$ 会坠落在农场上，其中第 $i$ 颗流星会在时刻 $T_i$ （ $0 \leq T _ i \leq 1000$ ）砸在坐标为 $(X_i,Y_i)(0\leq X_i\leq 300$ ， $0\leq Y_i\leq 300)$ 的格子里。流星的力量会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。贝茜在时刻 $0$ 开始行动，她只能在会在横纵坐标 $X,Y\ge 0$ 的区域中，平行于坐标轴行动，每 $1$ 个时刻中，她能移动到相邻的（一般是 $4$ 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被流星撞击或烧焦，那么贝茜只能在 $t$ 之前的时刻在这个格子里出现。贝茜一开始在 $(0,0)$ 。请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $−1$ 。输入共 $M+1$ 行，第 $1$ 行输入一个整数 $M$ ，接下来的 $M$ 行每行输入三个整数分别为 $X_i, Y_i, T_i$ 。输出贝茜到达安全地点所需的最短时间，如果不可能，则为 $-1$ 。

首先从“最少”时间这个关键词推断出需要该问题需要使用广搜算法。对于任意一个点而言，我们不但需要维护其 $x、y$ 坐标，同时需要维护这个点的步数，被摧毁的时间以及是否被访问过。

struct node
{
    int x;
    int y;
    int step;
    int time;
    bool vis;

    node(int x = -1, int y = -1, int step = -1, int time = -1, bool vis = false)
    {
        this->x = x;
        this->y = y;
        this->step = step;
        this->time = time;
        this->vis = vis;
    }

}coordinate[303][303];

之后，我们需要标记每个可能被烧焦的格子的被烧焦的时间，在bfs过程中，如果我们将要走到一个被烧焦的格子时，立即返回即可。该操作可以在读取数据时进行。

for (int i = 0; i < M; ++i)
    {
        int x, y, t;
        cin >> x >> y >> t;


        for (int j = 0; j < 5; ++j)
        {
            int cx = x + dx[j];
            int cy = y + dy[j];

            if (cx < 0 || cy < 0)
                continue;

            if (coordinate[cx][cy].time == -1 || coordinate[cx][cy].time > t)
                coordinate[cx][cy].time = t;
        }
    }

之后开始爆搜即可。

建队及压首。建立不定长队列，并将起始点压入队列。

int bfs()
{
    coordinate[0][0].step = 0;
    coordinate[0][0].vis = 1;
    req.emplace(coordinate[0][0]);
}

遍历队列。遍历队列中存在的每一个点。

while (!req.empty())

产生情况。取出目前点，分别向可行的四个方向移动，如果该点以及被访问过或者该点已经烧焦，则不产生前往该点的情况。

auto head = req.front();
req.pop();

for (int i = 0; i < 4; ++i)
{
   int cx = head.x + dx[i];
   int cy = head.y + dy[i];

   if (cx < 0 || cy < 0 || coordinate[cx][cy].vis)
       continue;
       if (coordinate[cx][cy].time == -1)
           return head.step + 1;
}

向下搜索。将产生的所有新点压入队列。

if (head.step + 1 < coordinate[cx][cy].time)
{
    coordinate[cx][cy].vis = true;
    coordinate[cx][cy].step = head.step + 1;
    req.emplace(coordinate[cx][cy]);
}

通过管理多个状态，我们成功帮助Bessie找到了一个安全的地方。

#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int x;
    int y;
    int step;
    int time;
    bool vis;

    node(int x = -1, int y = -1, int step = -1, int time = -1, bool vis = false)
    {
        this->x = x;
        this->y = y;
        this->step = step;
        this->time = time;
        this->vis = vis;
    }

}coordinate[303][303];

bool vis[303][303];
int dx[] = { 1,-1,0,0,0 };
int dy[] = { 0,0,-1,1,0 };
queue<node> req;
int bfs();

int main()
{
    for (int i = 0; i < 303; ++i)
    {
        for (int j = 0; j < 303; ++j)
        {
            coordinate[i][j].x = i;
            coordinate[i][j].y = j;
        }
    }

    int M;
    cin >> M;

    for (int i = 0; i < M; ++i)
    {
        int x, y, t;
        cin >> x >> y >> t;


        for (int j = 0; j < 5; ++j)
        {
            int cx = x + dx[j];
            int cy = y + dy[j];

            if (cx < 0 || cy < 0)
                continue;

            if (coordinate[cx][cy].time == -1 || coordinate[cx][cy].time > t)
                coordinate[cx][cy].time = t;
        }
    }

    cout << bfs();

    return 0;
}

int bfs()
{
    coordinate[0][0].step = 0;
    coordinate[0][0].vis = 1;
    req.emplace(coordinate[0][0]);

    while (!req.empty())
    {
        auto head = req.front();
        req.pop();

        for (int i = 0; i < 4; ++i)
        {
            int cx = head.x + dx[i];
            int cy = head.y + dy[i];

            if (cx < 0 || cy < 0 || coordinate[cx][cy].vis)
                continue;

            if (coordinate[cx][cy].time == -1)
                return head.step + 1;

            if (head.step + 1 < coordinate[cx][cy].time)
            {
                coordinate[cx][cy].vis = true;
                coordinate[cx][cy].step = head.step + 1;
                req.emplace(coordinate[cx][cy]);
            }
        }
    }
    return -1;
}