算法讲解062 必备宽度优先遍历及其扩展

来源：算法讲解062【必备】宽度优先遍历及其扩展　·　2026-10-27

依据：视频字幕 2000 字

一句话概括

宽度优先遍历（Breadth-First Search, BFS）是从起点出发按「距离层」逐层扩展的图/网格遍历方法，天然求出无权图单源最短路，并可通过「多源入队」「0-1 BFS」「分层 BFS」等扩展解决一大类最短路、连通块、最小步数问题。

它解决什么问题

无权图（边权全为 1）上从源点 \(s\) 到所有点的最短距离 / 最短步数。
网格图（上下左右 / 八方向）从起点走到终点的最少步数、能否到达。
多源最短路：多个起点同时扩散（如「每个点到最近源点的距离」）。
边权只有 0 和 1 的最短路（0-1 BFS，用双端队列）。
连通块 / 分层扩散 / 拓扑式按层处理（如「每轮同时感染」类问题）。
状态空间搜索：把「局面」当点、一次操作当边，求最少操作次数（如八数码、倒水问题）。

基础知识（前置概念，用大白话解释）

图（Graph）：点（顶点，vertex）和边（edge）的集合。边有方向的叫有向图，没方向的叫无向图。
邻接表（Adjacency List）：每个点存一个「它能一步走到哪些点」的列表，常用 vector<vector<int>>。点数 \(n\)、边数 \(m\) 时空间 \(O(n+m)\)。
队列（Queue）：先进先出（FIFO）的容器，C++ 用 std::queue<int>，需要两端操作时用 std::deque<int>。
距离数组（dist）：dist[v] 表示从源点到 \(v\) 的最短步数，初始化为 -1 表示「没访问过」。
无权图：每条边代价都相同（通常视为 1）。BFS 只在这种图上保证最短路；边权不同要用 Dijkstra。
网格图（Grid）：把每个格子 \((i,j)\) 编号成 i*m+j，四方向邻居是 (i±1,j)、(i,j±1)，注意边界判断。

原理（为什么这么做是对的，尽量给直觉）

BFS 用队列保证「先发现的点先扩展」。关键性质：队列里的点，其距离值最多只有两种，且单调不降（先是 \(d\)，后面是 \(d+1\)）。

直觉：从源点 \(s\) 出发，距离为 0 的只有 \(s\)；把 \(s\) 弹出时把距离 1 的点全部入队；这些距离 1 的点依次弹出时把距离 2 的点入队……于是点是按距离从小到大被处理的。因此第一次访问到某个点 \(v\) 时，走的就是最短路径——因为如果存在更短路径，那条路径上的前驱会更早被处理，\(v\) 会更早入队，矛盾。

形式化一点：设 \(v\) 第一次被访问时距离为 \(d(v)\)，则所有距离 \(< d(v)\) 的点都已被弹出，所有距离 \(= d(v)\) 的点要么已弹出要么在队列中；\(v\) 只能由距离 \(d(v)-1\) 的点扩展而来，所以 \(d(v)\) 就是最短路长度。

多源 BFS 同理：把所有源点距离设为 0 一起入队，等价于加一个「超级源点」连向所有源点，求出的是「到最近源点的距离」。

0-1 BFS：边权为 0 时走 0 边不应增加层数，所以 0 边扩展的点塞到队头（push_front），1 边扩展的点塞到队尾（push_back），队列仍保持距离单调，等价于一个小根堆但常数更小。

步骤（编号，可照着写）

建图：读入边，往邻接表里加边（无向图加两次）。
初始化 dist 数组全为 -1（或 INF），源点 dist[s] = 0。
源点入队。
当队列非空：

1. 弹出队头 u；

2. 遍历 u 的所有邻居 v；

3. 若 dist[v] == -1（未访问），则 dist[v] = dist[u] + 1，v 入队。

队列空时结束，dist 即答案；dist[t] == -1 表示不可达。

多源版本：第 2、3 步把所有源点 dist = 0 并全部入队。

0-1 BFS 版本：第 4.1 步用 deque 弹出队头；第 4.3 步若边权为 0 则 push_front，为 1 则 push_back；允许「松弛更优」而不是只判未访问（见代码）。

样例（一个具体小例子，带每步变化）

无向图，5 个点，边：1-2, 1-3, 2-4, 3-4, 4-5，源点 1（下标从 1）。

初始：dist = [0, -1, -1, -1, -1]，队列 [1]。

| 步骤 | 弹出 | 邻居 | 动作 | 队列 | dist[1..5] |

|---|---|---|---|---|---|

| 1 | 1 | 2,3 | 都未访问，dist=1，入队 | [2,3] | 0,1,1,-1,-1 |

| 2 | 2 | 1,4 | 1 已访问；4 未访问，dist=2，入队 | [3,4] | 0,1,1,2,-1 |

| 3 | 3 | 1,4 | 都已访问，跳过 | [4] | 0,1,1,2,-1 |

| 4 | 4 | 2,3,5 | 2,3 已访问；5 未访问，dist=3，入队 | [5] | 0,1,1,2,3 |

| 5 | 5 | 4 | 已访问 | [] | 0,1,1,2,3 |

结果：到 5 的最短路是 1→2→4→5，长度 3。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（普通 BFS + 多源 BFS + 0-1 BFS 三种写法）：

from collections import deque

def bfs(n, adj, s):
    # n 个点，编号 0..n-1；adj[u] 是 u 的邻居列表
    dist = [-1] * n
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def multi_source_bfs(n, adj, sources):
    dist = [-1] * n
    q = deque()
    for s in sources:
        if dist[s] == -1:      # 去重，防止重复入队
            dist[s] = 0
            q.append(s)
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def zero_one_bfs(n, adj, s):
    # adj[u] 存 (v, w)，w 只能是 0 或 1
    INF = float('inf')
    dist = [INF] * n
    dist[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

C++（竞赛风，普通 BFS + 多源 + 0-1 BFS）：

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

// 普通 BFS：n 个点（0..n-1），无向图，源点 s
// 返回 dist 数组，-1 表示不可达
vector<int> bfs(int n, const vector<vector<int>>& adj, int s) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// 多源 BFS：sources 里所有点距离为 0，求每个点到最近源点的距离
vector<int> multiSourceBfs(int n, const vector<vector<int>>& adj,
                           const vector<int>& sources) {
    vector<int> dist(n, -1);
    queue<int> q;
    for (int s : sources) {
        if (dist[s] == -1) {          // 去重
            dist[s] = 0;
            q.push(s);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// 0-1 BFS：边权只有 0/1，adj[u] 存 {v, w}
vector<int> zeroOneBfs(int n, const vector<vector<pair<int,int>>>& adj, int s) {
    vector<int> dist(n, INF);
    deque<int> dq;
    dist[s] = 0;
    dq.push_back(s);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
        }
    }
    return dist;
}

// 网格 BFS 示例：n 行 m 列，'.' 可走 '#' 不可走，求 (sx,sy) 到 (tx,ty) 最少步数
int gridBfs(const vector<string>& g, int sx, int sy, int tx, int ty) {
    int n = g.size(), m = g[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    static const int dx[4] = {-1, 1, 0, 0};
    static const int dy[4] = {0, 0, -1, 1};
    queue<pair<int,int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) return dist[x][y];
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 按需调用上面的函数
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

时间：\(O(n + m)\)，每个点入队至多一次、每条边被检查至多两次（无向图）。最好/平均/最坏都是这个量级，与图结构无关。
空间：\(O(n + m)\)（邻接表 + dist + 队列）。
常数：很小。BFS 是线性算法里常数最小的一类，queue<int> 比 priority_queue 快得多；0-1 BFS 用 deque 比 Dijkstra 的堆快约一个 log。网格图 \(n \times m\) 到 \(2\times10^6\) 级别用 BFS 完全没问题，注意别用 vector<vector<int>> 存大网格 dist 时反复分配（可压成一维 vector<int> dist(n*m, -1)）。

竞赛里什么时候用（看到什么题面特征就该想到它）

「最少步数」「最少操作次数」「最短时间」，且每步代价相同 → BFS。
网格图、迷宫、上下左右移动、有障碍 → 网格 BFS。
「多个起点同时出发」「每个格子到最近的 X 的距离」→ 多源 BFS。
边权只有 0 和 1（如「免费传送一次」「普通边代价 1、特殊边代价 0」）→ 0-1 BFS。
「每轮同时扩散 / 同时感染 / 同时淹没」→ 分层 BFS（按 dist 分层统计）。
状态空间小（状态数 \(\le 10^6\) 左右）且求最少操作 → 把状态编码成整数做 BFS（如八数码、倒水、开关灯）。
求连通块个数 / 每个连通块大小 → BFS/DFS 均可，BFS 不怕递归爆栈。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

#include <bits/stdc++.h>
using namespace std;

// 通用 BFS 模板：n 点 0..n-1，无向图，源点 s
// 需要多源时把 sources 全部 dist=0 入队即可
vector<int> bfs(int n, const vector<vector<int>>& adj, int s) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return dist;
}

// 网格 BFS 模板：n 行 m 列，g[x][y]=='.' 可走
// 返回 (tx,ty) 的最少步数，不可达返回 -1
int gridBfs(const vector<string>& g, int sx, int sy, int tx, int ty) {
    int n = (int)g.size(), m = (int)g[0].size();
    vector<int> dist(n * m, -1);
    auto id = [m](int x, int y) { return x * m + y; };
    static const int dx[4] = {-1, 1, 0, 0};
    static const int dy[4] = {0, 0, -1, 1};
    queue<int> q;
    dist[id(sx, sy)] = 0;
    q.push(id(sx, sy));
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        int x = cur / m, y = cur % m;
        if (x == tx && y == ty) return dist[cur];
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == '#' || dist[id(nx, ny)] != -1) continue;
            dist[id(nx, ny)] = dist[cur] + 1;
            q.push(id(nx, ny));
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}

边界与易错点（WA 的常见原因，越具体越好）

忘记判 dist[v] == -1：不加判断会重复入队，队列爆炸甚至死循环（有环图）。
多源 BFS 源点重复入队：sources 里有重复点时要先判 dist[s] == -1 再入队，否则同一源点入队多次，虽然结果对但常数变差，某些题会 T。
网格边界：nx < 0 || nx >= n || ny < 0 || ny >= m 四个条件一个都不能少；n、m 别写反。
下标从 0 还是 1：读入 1-based 的题记得减 1，或者数组开 n+1；混用是 WA 重灾区。
多测清空：dist、邻接表、队列每轮都要清空；用 vector 局部变量最省心，全局数组要手动 fill。
不可达输出：题目常要求输出 -1 或特定值，dist[t] == -1 时别直接输出 dist[t]。
0-1 BFS 用「松弛」而不是「只判未访问」：0 边可能让已访问点距离变小，必须写 if (dist[u] + w < dist[v])，否则错。
0-1 BFS 弹出后不判 stale：与 Dijkstra 不同，0-1 BFS 允许同一点多次入队，弹出时不需要判「是否已确定」，但距离更新必须严格小于才入队，否则会无限入队。
边权不全是 1 却用普通 BFS：只要有一条边权 \(\ne 1\)，普通 BFS 就不保证最短路，必须换 Dijkstra / 0-1 BFS / SPFA。
状态 BFS 忘记编码/去重：状态空间搜索必须用 dist 或 visited 记录已访问状态，否则指数爆炸。
int 溢出：距离最大可能到 \(n\) 级别，一般 int 够；但若题目把距离当权值累加（如带权最短路），要 long long。

同类题 / 变形（说清楚怎么改）

多源最短路：把所有源点 dist = 0 一起入队，其余不变。典型：「腐烂的橘子」「01 矩阵」。
0-1 BFS：邻接表存 (v, w)，w ∈ {0,1}，0 边 push_front、1 边 push_back，判据改成松弛。典型：「最少换乘」「免费次数」类。
分层 BFS / 按层统计：在弹出前记录当前队列大小 sz，循环 sz 次作为一层，层数即距离。典型：「每轮同时扩散」「最短时间」。
双向 BFS（Bidirectional BFS）：从起点和终点同时 BFS，每次扩展队列较小的一侧，相遇即最短路。状态空间大但答案浅时（如单词接龙）能大幅降复杂度，从 \(O(b^d)\) 降到 \(O(b^{d/2})\)。
BFS + 状态压缩：把局面编码成整数（如八数码用康托展开或 int 编码），在状态图上 BFS。
BFS 求连通块：每次从未访问点出发 BFS，标记整块，统计块数/块大小。
**A\*（A-star）**：BFS 加启发式估价函数，用于大状态空间最短路（竞赛较少，面试常问）。

常见坑

用 list 或 map 存邻接表：常数巨大，1e5 级别就可能 T，一律 vector。
用 queue<pair<int,int>> 存网格坐标而不压成一维：可以，但压成一维 int 更快、更省。
deque 的 push_front 在 0-1 BFS 里用错方向（0 边应进队头）。
多测时全局 dist 没清空，第二组数据直接错。
递归 DFS 求连通块在 1e6 点链状图上爆栈，BFS 没这个问题（这也是选 BFS 的理由之一）。
网格题把 n（行）和 m（列）在 id = x*m+y 里写反。
输出格式：多测之间空行、末尾换行，PE 也是 WA。

拓展（变体、实际用途、面试常问）

实际用途：社交网络「几度好友」、网页爬虫按层抓取、迷宫寻路、网络广播最短跳数、游戏 AI 的格子寻路。
面试常问：BFS 与 DFS 的区别与适用场景；为什么 BFS 能求无权图最短路；双向 BFS 的复杂度分析；0-1 BFS 与 Dijkstra 的关系（0-1 BFS 是 Dial 算法在 \(C=1\) 时的特例）。
变体：多源 BFS、双向 BFS、0-1 BFS、分层 BFS、BFS 序（按距离排序）、BFS 树（最短路树）。
与 Dijkstra 的关系：Dijkstra 是「带权 BFS」，用堆代替队列；边权全 1 时退化为 BFS，边权 0/1 时退化为 0-1 BFS。

自测 3 题（题目 + 折叠答案）

题 1：\(n\) 个点 \(m\) 条边的无向无权图，求 1 号点到 \(n\) 号点的最短路径长度，不可达输出 -1。\(n, m \le 2\times10^5\)。

答案

标准 BFS：dist[1]=0 入队，逐层扩展，最后输出 dist[n]（-1 表示不可达）。时间 \(O(n+m)\)。

vector<int> dist(n + 1, -1);
queue<int> q;
dist[1] = 0; q.push(1);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}
cout << dist[n] << '\n';

</details>

题 2：\(n \times m\) 网格，每个格子是 0 或 1，求每个 1 到最近的 0 的距离（曼哈顿距离，四方向）。\(n,m \le 1000\)。

答案

多源 BFS：把所有 0 的格子 dist = 0 入队，BFS 扩散，dist 即为答案。时间 \(O(nm)\)。

vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int,int>> q;
for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        if (g[i][j] == 0) { dist[i][j] = 0; q.push({i, j}); }
// 之后标准 BFS 四方向扩展

</details>

题 3：有 \(n\) 个城市，\(m\) 条航线，每条航线要么是「普通航班」代价 1，要么是「免费航班」代价 0（但免费航班总共只能用 \(k\) 次，\(k \le 10\)）。求 1 到 \(n\) 的最小代价。\(n,m \le 10^5\)。

答案

分层图 + 0-1 BFS：状态 (u, used) 表示在城市 u、已用 used 次免费航班，共 \(n(k+1)\) 个状态。普通边 (u,used) -> (v,used) 权 1；免费边 (u,used) -> (v,used+1) 权 0（used < k 时）。在分层图上跑 0-1 BFS，答案取 min(dist[n][used])。时间 \(O((n+m)k)\)。

// 状态 id = u * (k + 1) + used
vector<int> dist(n * (k + 1), INF);
deque<int> dq;
dist[0 * (k + 1) + 0] = 0; dq.push_back(0);
while (!dq.empty()) {
    int cur = dq.front(); dq.pop_front();
    int u = cur / (k + 1), used = cur % (k + 1);
    for (auto [v, w] : adj[u]) {          // w=1 普通, w=0 免费
        int nu = used + (w == 0 ? 1 : 0);
        if (nu > k) continue;
        int nxt = v * (k + 1) + nu;
        if (dist[cur] + w < dist[nxt]) {
            dist[nxt] = dist[cur] + w;
            if (w == 0) dq.push_front(nxt);
            else        dq.push_back(nxt);
        }
    }
}

</details>

算法讲解062 必备 宽度优先遍历及其扩展

一句话概括

它解决什么问题

基础知识（前置概念，用大白话解释）

原理（为什么这么做是对的，尽量给直觉）

步骤（编号，可照着写）

样例（一个具体小例子，带每步变化）

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

竞赛里什么时候用（看到什么题面特征就该想到它）

竞赛模板（C++，可直接背下来的写法；变量名清楚）

边界与易错点（WA 的常见原因，越具体越好）

同类题 / 变形（说清楚怎么改）

常见坑

拓展（变体、实际用途、面试常问）

自测 3 题（题目 + 折叠答案）

算法讲解062 必备宽度优先遍历及其扩展