宽度优先搜索（BFS）

前置知识

注意该算法的前置知识为队列（queue）,如果没有学习，请点击这里进行学习

BFS的介绍

BFS（宽度优先搜索 Breadth-First Search）是一种用于图的遍历或搜索的算法。它从一个节点开始，逐层遍历图中的所有节点。BFS通常用队列来实现，因为它需要按照节点的发现顺序来访问它们。

工作原理

BFS的工作原理可以总结为以下几个步骤

循环：只要队列不为空，就执行以下操作：
出队一个节点（我们称之为当前节点）。
访问当前节点的所有未访问的邻节点（子节点）。
将每个未访问的邻居节点（子节点）标记为已访问，并将其入队。

BFS算法的特点

层级遍历：它按层级顺序访问节点，这意味着它会先访问所有与源节点相邻的节点，然后是那些节点的邻居，以此类推。
最短路径：在无权图中，BFS可以找到从源节点到其他任何节点的最短路径。
时间复杂度：对于有V个顶点和E条边的图，BFS的时间复杂度是O(V+E)。
空间复杂度：在最坏的情况下，BFS可能需要O(V)的空间来存储所有节点的访问状态。

图示演示

下面进行进行图示演示：

首先1为根节点
BFS 示例树结构，节点 1 为起始根节点

假如我们使用的是DFS，那么DFS序如下：
同一棵树的 DFS 遍历顺序

如果我们使用BFS，那么可以理解为按照深度对图进行分层，例如下图，分为1-4共4层，每次遍历先遍历完上一层的所有节点，接着再遍历下一层，首先根节点1入队，遍历完1之后，1的所有子节点入队，1做一次标记并且退队。
BFS 按节点深度将树划分为四层

然后接着对队列中的元素2、3、4、5进行遍历，遍历完2后将2的子节点入队并且对2做标记且让2出队，后续接着遍历完3、4、5，各自子节点入队后各自再做一次标记并退队。
BFS 从根节点开始逐层扩展的访问顺序

接着遍历队列中的元素，直到最后一个元素退队后没有新的元素入队，即队列为空，遍历结束。
BFS 完成整棵树遍历的访问顺序

例题：马的遍历

依然是DFS中出现的这道Luogu例题： https://www.luogu.com.cn/problem/P1443 我们接下来用BFS的方法解答一下

int dist[401][401]; //dist[i][j]表示从起点到(i,j)的最少步数
struct Node { int x, y; };
queue<Node> q;
int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

memset(dist, -1, sizeof(dist));
dist[sx][sy] = 0;
q.push({sx, sy});

接下来开始BFS，代码如下

while (!q.empty()) {
    Node cur = q.front(); q.pop();
    for (int i = 0; i < 8; i++) {
        int nx = cur.x + dx[i], ny = cur.y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[cur.x][cur.y] + 1;
        q.push({nx, ny});
    }
}

然后我们就完成了对所有情况的遍历，接着对答案进行输出

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) cout << left << setw(5) << dist[i][j];
    cout << '\n';
}

然后我们就完成了这道题目。全部代码如下

点击展开完整代码

#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int dist[401][401];
struct Node { int x, y; };
int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;
    memset(dist, -1, sizeof(dist));
    queue<Node> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[cur.x][cur.y] + 1;
            q.push({nx, ny});
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << left << setw(5) << dist[i][j];
        cout << '\n';
    }
    return 0;
}

双端队列BFS（0-1 BFS）

普通BFS要求每次移动的代价相同。如果边权只有$0$和$1$，仍然可以保持按最短距离处理节点，只是普通队列需要换成双端队列deque。

经过权值为$0$的边，距离没有增加，将新状态放到队首；
经过权值为$1$的边，距离增加$1$，将新状态放到队尾。

deque<int> q;
dist[s] = 0;
q.push_front(s);
while (!q.empty()) {
    int u = q.front(); q.pop_front();
    for (auto [v, w] : g[u]) if (dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        if (w == 0) q.push_front(v);
        else q.push_back(v);
    }
}

这里不能只用“是否访问过”判断状态，因为一个节点第一次被发现时，距离仍然可能被另一条路径缩短。和最短路一样，应当根据dist是否变小决定是否更新。

例题：AtCoder ABC176 D Wizard in Maze

题目链接：AtCoder ABC176 D Wizard in Maze

在迷宫中，上下左右走到相邻空地不消耗魔法；也可以使用一次魔法，移动到以当前位置为中心的$5\times5$范围内任意空地。求到达终点最少使用多少次魔法。

把每个空地看成一个节点：普通移动的边权为$0$，使用魔法的边权为$1$，问题正好变成0-1最短路。

双端队列中可能同时存在同一位置的旧记录。使用done标记已经正式取出并处理的状态；0-1 BFS会按照距离从小到大取出节点，因此第一次正式处理时的距离就是最短距离。

点击展开完整代码

/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
const int INF = 1e9;

struct Node { int x, y; };
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w, sx, sy, tx, ty;
    cin >> h >> w >> sx >> sy >> tx >> ty;
    sx--; sy--; tx--; ty--;
    vector<string> s(h);
    for (string &row : s) cin >> row;
    vector<vector<int>> dist(h, vector<int>(w, INF));
    vector<vector<bool>> done(h, vector<bool>(w));
    deque<Node> q;
    dist[sx][sy] = 0;
    q.push_front({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop_front();
        if (done[x][y]) continue;
        done[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] == '#') continue;
            if (dist[nx][ny] > dist[x][y]) { 
                dist[nx][ny] = dist[x][y]; 
                q.push_front({nx, ny}); 
            }
        }
        for (int i = -2; i <= 2; i++) {
            for (int j = -2; j <= 2; j++) {
                int nx = x + i, ny = y + j;
                if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] == '#') continue;
                if (dist[nx][ny] > dist[x][y] + 1) { 
                    dist[nx][ny] = dist[x][y] + 1; 
                    q.push_back({nx, ny}); 
                }
            }
        }
    }
    cout << (dist[tx][ty] == INF ? -1 : dist[tx][ty]) << '\n';
    return 0;
}

每个格子的候选移动数量是常数，时间复杂度和空间复杂度均为$O(hw)$。

多源BFS

有些题目不是从一个起点出发，而是要求每个位置到“最近起点”的距离。分别从每个起点运行一次BFS会重复遍历大量状态。

多源BFS只需要在搜索开始前，把所有起点的距离设为$0$并同时加入队列，后面的过程与普通BFS完全相同。它等价于新建一个虚拟起点，再用权值为$0$的边连接所有真实起点。

1	for (auto s : sources) { dist[s] = 0; q.push(s); }

由于所有起点处在同一层，BFS仍然按照距离递增的顺序扩展。某个位置第一次入队时，得到的就是它到所有起点中的最短距离。

例题：AtCoder ABC383 C Humidifier 3

题目链接：AtCoder ABC383 C Humidifier 3

网格中包含墙、空地和若干个加湿器。一个空地如果能从任意加湿器出发，在不穿过墙的情况下用不超过$d$步到达，就会被加湿。求被加湿的格子数量。

所有加湿器都是距离为$0$的起点。把它们一起加入队列，再进行一次BFS，就能得到每个格子到最近加湿器的距离。距离达到$d$以后不再向外扩展即可。

点击展开完整代码

/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Node { int x, y; };
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w, d;
    cin >> h >> w >> d;
    vector<string> s(h);
    for (string &row : s) cin >> row;
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<Node> q;
    int ans = 0;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (s[i][j] == 'H') {
        dist[i][j] = 0;
        q.push({i, j});
        ans++;
    }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (dist[x][y] == d) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}