12.3　广度优先搜索

学习目标：学完本节，你能

用队列实现 BFS，并说清它和 DFS 的本质区别；
用"前驱数组"还原出路径；
解释 BFS 为什么一定找到最短路径 —— 这个性质的价值和边界。

先修：12.2（DFS）、9.3（树的层序遍历）、5.2（队列）。 固定术语：广度优先搜索、层、前驱数组。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：水波纹 vs 钻探

12.2 节的 DFS 像钻探 —— 认准一个方向钻到底，钻不动了退回换方向。

BFS 像水波纹 —— 从中心一圈一圈向外扩散。

  DFS:  0 → 1 → 3 → 2 → 4      一条路走到底
  BFS:  第 0 层: 0
        第 1 层: 1 2
        第 2 层: 3 4
        第 3 层: 5

容器决定了行为（12.2 节的图用同一个）：

	容器	取出顺序	效果
DFS	栈	后进先出	一条路走到底
BFS	队列	先进先出	一层一层扩散

为什么队列能做到"一层一层"？

因为当前层的所有顶点都会比下一层的先入队 —— 所以出队时，当前层一定会被优先处理完。

二、实现

/// <summary>BFS：一层一层扩散，记录每个顶点的距离和前驱。</summary>
static (int[] Dist, int[] Prev) Bfs(Graph g, int start, bool trace = false)
{
    var dist = new int[g.VertexCount];
    var prev = new int[g.VertexCount];
    Array.Fill(dist, -1);              // -1 表示「没访问过」
    Array.Fill(prev, -1);
    var queue = new Queue<int>();

    dist[start] = 0;
    queue.Enqueue(start);

    int level = 0;
    while (queue.Count > 0)
    {
        int levelSize = queue.Count;    // ★ 这一层有多少个（9.3 节的技巧）
        if (trace) Console.WriteLine($"    第 {level} 层:");

        for (int i = 0; i < levelSize; i++)
        {
            int v = queue.Dequeue();
            if (trace) Console.Write($"      {v}");

            foreach (int next in g.Neighbors(v))
            {
                if (dist[next] != -1) continue;    // 已经访问过
                dist[next] = dist[v] + 1;          // 距离 = 前一个的距离 + 1
                prev[next] = v;                    // 记录前驱，用来还原路径
                queue.Enqueue(next);
            }
        }
        if (trace) Console.WriteLine();
        level++;
    }

    return (dist, prev);
}

三处和 DFS 的对应关系：

	DFS	BFS
容器	`Stack<int>`	`Queue<int>`
访问标记	`bool[] visited`	`int[] dist`（`-1` 表示没访问过，同时记录了距离）
额外信息	无	`int[] prev`（前驱，用来还原路径）

dist 数组一物两用：既当"访问标记"（-1 表示没访问过），又当"距离记录"。

这是 BFS 比 DFS 多做的事 —— 也是它能回答"最短路径"这个问题的原因。

实测分层追踪（从 0 出发）：

注意第 1 层：0 的两个邻居 1、2 都出来了 —— 它们在处理 0 的时候被入队，所以会连续出队。

三、`levelSize` 那一行

int levelSize = queue.Count;    // ★

这一行是"分层"的关键（9.3 节讲过）。

为什么必须在循环开始前取？

因为在遍历这一层的过程中，会把下一层的顶点加入队列 —— queue.Count 一直在变。

处理第 0 层时：
  队列开始: [0]              levelSize = 1
  取出 0，把 1、2 加进去 -> [1, 2]
  循环 1 次结束
  此时队列里正好是第 1 层: [1, 2]  ✓

如果没有 levelSize，你只能得到一个"大杂烩"的访问顺序，分不清哪个顶点属于哪一层。

对 BFS 来说，"层"就是"距离起点的步数" —— 丢掉层信息，就等于丢掉了 BFS 最值钱的东西。

四、还原路径：`prev` 数组

BFS 跑完之后，每个顶点都记录了"我是从哪个顶点过来的"（prev）。

沿着 prev 往回走，就能还原出路径：

static List<int>? ReconstructPath(int[] prev, int start, int target)
{
    if (prev[target] == -1 && target != start) return null;    // 不可达

    var path = new List<int>();
    for (int v = target; v != -1; v = prev[v])
        path.Add(v);

    path.Reverse();                    // 从终点倒推到起点，所以最后要反转
    return path[0] == start ? path : null;
}

实测：

  0 到 5: 0 -> 2 -> 4 -> 5（3 步）
  0 到 3: 0 -> 1 -> 3（2 步）
  1 到 5: 1 -> 0 -> 2 -> 4 -> 5（4 步）
  2 到 2: 2（0 步）

⚠️ 一个必须注意的坑：prev 数组是"从某个起点出发"的 BFS 树。

要查其他起点的路径，必须从那个起点重新跑一次 BFS。

我第一版代码就踩了这个坑 —— 用"从 0 出发"的 prev 去还原"从 1 到 5"的路径，结果全是错的。

这是 BFS 和 DFS 的一个共同限制：一次遍历只能回答"从一个起点出发"的问题。

如果要回答"任意两点间的最短路径"，需要跑 $V$ 次 BFS（每次换一个起点）—— 那是 $O(V(V+E))$，通常太慢。要多源最短路，得用 13.3 节的 Dijkstra。

五、BFS 为什么一定找到最短路径

这是 BFS 相对 DFS 最核心的优势。

因为 BFS 是【按距离一层一层】扩展的。

一个顶点第一次被访问时，它的距离就已经确定了 —— 因为所有距离更小的顶点都已经处理完了，不可能有更短的路径。

换句话说：

  第 0 层：起点自己           （距离 0）
  第 1 层：起点的所有邻居      （距离 1）
  第 2 层：距离 2 的所有顶点   （距离 2）
  ...

当你第一次遇到目标顶点时，它必然在所有"更近的层"都处理完之后才出现 —— 所以这个距离就是最短的。

实测验证（随机图上对比 BFS 距离与暴力枚举的最短距离）：

  实测验证（随机图上对比 BFS 距离与暴力最短距离）：
    对比了 20 张随机图 × 12 个目标点 = 240 组
    不一致的组数: 0
    BFS 的距离与暴力最短距离完全一致 ✓

验证方法：对每张随机图，用暴力 DFS 枚举所有简单路径求出真正的最短距离，再和 BFS 算出的距离逐一对比。

240 组全部一致 —— 这印证了 BFS 的正确性。

这个"第一次到达就是最短"的性质，依赖一个前提：每条边的"代价"相同。

12.1 节说过，边可以带权重（距离、时间、费用）。

如果边权不同，"步数最少"就不等于"总代价最小" —— 那时 BFS 就失效了。

带权图的最短路径要用 Dijkstra 算法（13.3 节）。它本质上就是"给 BFS 换了个容器"： 队列 → 优先队列（每次取距离最小的那个出来扩展）。

六、BFS vs DFS：跑一遍看差别

同一个图、同一个起点，两种遍历的对比：

  DFS:  0 -> 1 -> 3 -> 2 -> 4 -> ...      （一条路走到底）
  BFS:  0 -> 2 -> 4 -> 5                  （一层一层，且一定最短）

实测性能（200,000 个顶点的链式图）：

  BFS:     8.6 ms（访问 200,000 个顶点）
  DFS:     2.7 ms（访问 200,000 个顶点）

  复杂度都是 O(V + E)，但 BFS 实际慢了 3.21 倍。原因是：
    1. BFS 每次出队后还要维护 dist[] 和 prev[] 两个数组；
    2. Queue<T>（环形缓冲区）的常数比 Stack<T>（数组尾部操作）大。
  —— 这个差距是【常数级】的，不是量级差别。

注意"慢了 3.21 倍"这个数字 —— 它比我预期的"差不多"要大。

原因正是上面两条：BFS 多做的工作（维护两个数组 + 队列的常数）累积起来了。

但 BFS 多做的这些工作是值得的 —— 它换来了"距离"和"路径"这两样 DFS 给不了的信息。

七、空间开销：看的是不同的维度

BFS 和 DFS 的空间开销取决于图的【不同维度】。

实测（星形图：中心 0 连着 100,000 个叶子）：

  星形图：中心 0 连着 100,000 个叶子
  BFS 处理第 0 层时，会把 100,000 个叶子【全部】压进队列
  队列峰值大小 ≈ 100,000 —— 这就是 BFS 的内存代价：O(最宽的一层)

  对比【递归版 DFS】处理同一张图（栈深度 = 递归深度）：
  递归 DFS 的最大深度 = 1（栈上同时只有 2 个栈帧）

同一个图，一个是 100,000 的内存，一个是 1 的深度。

	BFS	DFS（递归版）
峰值取决于	最宽的一层	最深的路径
星形图（宽而浅）	100,000	1
链式图（窄而深）	1	200,000（会栈溢出）

所以"哪个更省空间"完全取决于图的形状。

一个实践推论：

图很宽 + 内存紧张 → 优先考虑 DFS

图很深 + 担心栈溢出 → 优先考虑 BFS（或把 DFS 改成迭代版）

注意上面的 DFS 结论针对【递归版】。 迭代版如果用"一次把所有邻居都压栈"的写法，栈峰值也可能很大 —— 这正是 12.2 节练习 12.2.5 讨论的"重复压栈"带来的空间问题。

八、练习

练习 12.3.1（手写 BFS）对下面的图，从 0 出发做 BFS，写出每一层的顶点和每个顶点的距离。

  0 —— 1 —— 3
  |         |
  2 —— 4 —— 5

练习 12.3.2（路径还原）接上题，BFS 跑完后 prev 数组是什么样的？写出从 0 到 5 的路径。

练习 12.3.3（判断）判断对错并说明理由： (a) BFS 一定比 DFS 慢，因为它要多维护两个数组。 (b) BFS 和 DFS 的空间复杂度都是 $O(V)$。 (c) BFS 找到的路径一定是最短的。 (d) 一次 BFS 就能回答"任意两点之间的最短路径"。

练习 12.3.4（工程判断）一个社交网络要计算"你和某个人之间的最短关系链"（六度分隔理论）。 (a) 应该用 BFS 还是 DFS？ (b) 如果用户量是 10 亿，一次 BFS 要遍历多少顶点？可行吗？ (c) 有什么改进方向？（提示：想想"从两端同时开始"。）

练习 12.3.5（挑战·双向 BFS） 双向 BFS 是从起点和终点同时开始 BFS，两边各扩展一层，直到它们"碰面"。

(a) 如果起点到终点的距离是 $d$，单向 BFS 要扩展多少个顶点（假设每个顶点平均有 $b$ 个邻居）？ (b) 双向 BFS 要扩展多少个？ (c) 两者差多少倍？

九、练习答案

12.3.1

图的结构：

  0 —— 1 —— 3
  |         |
  2 —— 4 —— 5

邻接表：0->[1,2]，1->[0,3]，2->[0,4]，3->[1,5]，4->[2,5]，5->[3,4]

BFS 过程（从 0 出发）：

层	处理	入队的新顶点	队列状态
第 0 层	0	1、2	`[1, 2]`
第 1 层	1	3	`[2, 3]`
第 1 层	2	4	`[3, 4]`
第 2 层	3	5	`[4, 5]`
第 2 层	4	（5 已访问）	`[5]`
第 3 层	5	—	`[]`

结果：

顶点	距离
0	0
1	1
2	1
3	2
4	2
5	3

分层：

  第 0 层: 0
  第 1 层: 1 2
  第 2 层: 3 4
  第 3 层: 5

验证：从 0 到 5，最短路径是 0 → 2 → 4 → 5（3 步）或 0 → 1 → 3 → 5（3 步），都是 3 步 ✓

12.3.2

prev 数组（-1 表示没有前驱，即起点）：

顶点	prev
0	-1（起点）
1	0
2	0
3	1
4	2
5	3

prev = [-1, 0, 0, 1, 2, 3]

从 0 到 5 的路径：

沿着 prev 从 5 倒推：

  5 → prev[5] = 3 → prev[3] = 1 → prev[1] = 0 → prev[0] = -1（停）

得到 5, 3, 1, 0，反转后是 0 → 1 → 3 → 5 ✓

另一条同样短的路径 0 → 2 → 4 → 5 为什么没被选中？

因为 BFS 只记录一个前驱。当 5 第一次被访问时（通过 3），它的 prev 就被定成 3 了。

后来从 4 也发现 5 时，dist[5] != -1，直接跳过了 —— 所以不会更新 prev。

所以 BFS 给出的是"一条"最短路径，不是"所有"最短路径。

12.3.3

(a) 错，方向不对。 BFS 确实多维护了两个数组，但这不是"一定更慢"的理由。

实测：200,000 个顶点的链式图上，BFS 8.6 ms，DFS 2.7 ms —— BFS 慢 3.21 倍。

但两者的复杂度都是 $O(V+E)$ —— 差距是常数级的，不是量级差别。

而且这个对比不公平：BFS 额外产出了"距离"和"路径"两样信息，而 DFS 那个版本什么都没记。

公平的比法是：让 DFS 也记录距离（它做不到唯一的最短距离）—— 那就不是同一个问题了。
(b) 错（不够精确）。 两者都是 $O(V)$ 的最坏空间，但实际峰值取决于图的形状： >

| | 峰值 | |---|---| | BFS | 最宽的一层 | | DFS（递归） | 最深的路径 |

实测（星形图，10 万叶子）：BFS 队列峰值 100,000，而递归 DFS 栈深度只有 1。

反过来，链式图上 BFS 队列只有 1 个元素，DFS 却要递归 20 万层（会栈溢出）。
(c) 对 —— 但有个前提：所有边的代价必须相同。

BFS 保证的是"边数最少"。如果边带权（比如两条路距离不同），"边数最少"不等于"总距离最短"。

带权图要用 Dijkstra（13.3 节）。
(d) 错。 一次 BFS 只能回答"从它那个起点出发"的最短路径 —— 因为 dist 和 prev 都是相对起点建立的。 >

要回答"任意两点"，需要对每个顶点各跑一次 BFS：

$$V \times O(V + E) = O(V^2 + VE)$$

对 10 万个顶点的图，这是天文数字。

这正是本节第四节那个坑的来源 —— 我第一版代码就是用"从 0 出发"的 prev 去还原"从 1 到 5"的路径，结果全错。

12.3.4

(a) 用 BFS。

因为要的是"最短关系链" = 最少步数，而 BFS 保证"第一次到达就是最短"。

DFS 不行 —— 它可能沿着一条很长的链绕过去，找到一条"10 步"的路径，却错过另一条"3 步"的。

(b) 10 亿个顶点时，不可行。

为什么？

BFS 要遍历所有距离 ≤ d 的顶点（$d$ 是起点到终点的距离）
假设每个人平均有 200 个好友（$b = 200$）
六度分隔意味着 $d$ 约等于 6

要扩展的顶点数量：

$$1 + b + b^2 + b^3 + b^4 + b^5 + b^6 \approx b^6 = 200^6 = 6.4 \times 10^{13}$$

6400 亿亿个顶点 —— 远超地球人口。

注意这里的关键：社交网络是"宽而浅"的图 —— 从任意一个人出发，几度之内就能覆盖全世界。

所以真正的问题不是"图太大"，而是"每一层太宽"。

(c) 改进方向：双向 BFS。

从起点和终点同时开始 BFS，两边各扩展一层，直到"碰面"。

效果：假设距离是 $d$，单向 BFS 要扩展约 $b^d$ 个顶点；双向 BFS 只要约 $2 \times b^{d/2}$。

对 $b = 200$、$d = 6$：

单向：$200^6 = 6.4 \times 10^{13}$
双向：$2 \times 200^3 = 1.6 \times 10^7$

差了 400 万倍。

这个优化的本质是：从"指数增长"变成"半个指数" —— 因为 $b^{d/2} \times b^{d/2} = b^d$，而双向把两次 $b^{d/2}$ 变成了可承受的量级。

代价：需要能"从终点反向搜索" —— 对社交网络来说，这意味着要能查出"谁关注了我"（反向边）。如果图只有单向边（比如网页链接），反向搜索就需要预先建立反向索引。

其他改进方向：

限制搜索深度 —— 搜索 3 度就停，通常够用（"你可能认识的人"就只算 2~3 度）。
启发式搜索 —— 用某些信息（比如地理位置、共同好友数）来指导"优先扩展哪些顶点"，这就是 A* 算法（超出本书范围）。
预计算 —— 对活跃用户预先算出"2 度以内的人"，用空间换时间。

12.3.5

(a) 单向 BFS：约 $b^d$ 个顶点。

推导：第 0 层 1 个、第 1 层 $b$ 个、第 2 层 $b^2$ 个…… 第 $d$ 层 $b^d$ 个。

总量是等比数列求和，由最后一项主导（3.2 节的摊还分析用过同样的推理）：

$$1 + b + b^2 + \cdots + b^d \approx b^d$$

(b) 双向 BFS：约 $2b^{d/2}$ 个顶点。

推导：

从起点出发，扩展 $\frac{d}{2}$ 层 → 约 $b^{d/2}$ 个顶点
从终点出发，也扩展 $\frac{d}{2}$ 层 → 约 $b^{d/2}$ 个顶点
两边在中间碰面

总共约 $2 b^{d/2}$。

(c) 差多少倍？

$$\frac{b^d}{2b^{d/2}} = \frac{b^{d/2}}{2}$$

对 $b = 10$、$d = 6$：

$$\frac{10^3}{2} = 500 \text{ 倍}$$

对 $b = 200$、$d = 6$：

$$\frac{200^3}{2} = 4 \times 10^6 \text{ 倍}$$

这个优化有多划算？

它把复杂度从 $O(b^d)$ 降到了 $O(b^{d/2})$ —— 相当于把指数砍了一半。

指数砍半的威力：如果 $b^d$ 是 100 万，$b^{d/2}$ 就只有 1000。

这在"搜索空间巨大"的场景里是决定性的 —— 所以双向 BFS 是所有"最短路径"类问题的标准优化，包括：

社交网络的"六度分隔"（练习 12.3.4）

地图导航（从起点和终点同时搜，现实中 80% 的最短路查询都能在毫秒级完成）

拼图 / 魔方求解（搜索空间巨大，单向根本搜不完）

一个重要的实现细节：双向 BFS 不是"两边各扩展一半就碰面" —— 因为两边的"层"不一定对齐。

正确的做法是：每次选择当前层数较少的那一边扩展一层，直到某个顶点同时出现在两边的访问集合里。

这个"碰面点"就是最短路径的中间点，两边的路径拼起来就是完整的最短路径。

十、常见错误

误区	纠正
忘记 `levelSize`	分不出层，丢掉"距离"这个最值钱的信息。必须在循环前取 `queue.Count`。
用 `prev` 数组查其他起点的路径	`prev` 是"从某个起点出发"的 BFS 树。换个起点必须重跑 BFS。
认为 BFS 一定比 DFS 慢	实测慢 3.21 倍，但那是常数级差异；而且 BFS 多产出了"距离 + 路径"。
认为 BFS/DFS 空间都是 $O(V)$ 就一样	峰值取决于图的形状：BFS 看宽度（星形图 100,000），DFS 看深度（星形图只有 1）。
用 BFS 求带权图的最短路径	BFS 只保证"边数最少"。带权图要用 Dijkstra（13.3 节）。
一次 BFS 回答"任意两点最短路"	做不到。要么跑 $V$ 次 BFS，要么用其他算法。

十一、本节总结

BFS 用队列，DFS 用栈 —— 容器决定了"一层层扩散"还是"一条路走到底"。
dist 数组一物两用：既当访问标记（-1 表示没访问过），又记录距离。
levelSize = queue.Count 是分层的关键（9.3 节），必须在循环前取。
prev 数组还原路径：从终点沿 prev 倒推到起点，再反转。
⚠️ prev 和 dist 都是"从某个起点出发"的 —— 换起点必须重跑 BFS。我第一版代码就踩了这个坑。
BFS 一定找到最短路径：因为第一次到达时距离就确定了。实测 240 组与暴力最短距离完全一致。
前提是"边权相同" —— 带权图要用 Dijkstra（13.3 节）。
空间开销看不同维度：BFS 看最宽的一层（星形图实测 100,000），DFS 看最深的路径（同一张图只有 1）。
双向 BFS 把 $O(b^d)$ 降到 $O(b^{d/2})$ —— 指数砍半，是所有最短路径搜索的标准优化。

下一节衔接：到这里，DFS 和 BFS 都讲完了。它们是所有图算法的骨架 —— 后面学的连通分量、环检测、拓扑排序、最短路，全都是在它们的基础上加一点点东西。下一节讲三个"加一点东西"就能解决的问题：数连通分量、检测环、判断二分图。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "12.3",
  "title": "广度优先搜索",
  "covered": [
    "BFS 的水波纹直觉与「队列 vs 栈」的本质区别",
    "BFS 完整实现（dist 一物两用 + prev 前驱数组）",
    "实测分层追踪与 levelSize 技巧",
    "prev 数组还原路径的实测（四条路径）",
    "「prev 是某个起点的 BFS 树」这个坑与修正",
    "BFS 保证最短路径的论证与 240 组暴力验证",
    "实测 BFS vs DFS 性能（8.6ms vs 2.7ms，慢 3.21 倍）与原因",
    "空间开销的两个维度（星形图：BFS 队列 100000 vs DFS 深度 1）",
    "双向 BFS 的 O(b^d) → O(b^(d/2)) 优化"
  ],
  "unresolved": [
    "连通分量与环检测留到 12.4",
    "Dijkstra 留到 13.3",
    "A* 算法超出本书范围"
  ],
  "canonical_terms": {
    "广度优先搜索（BFS）": "用队列一层一层扩散的图遍历策略",
    "层（Level）": "距离起点相同步数的顶点集合",
    "前驱数组（Prev）": "记录每个顶点是从哪个顶点访问到的，用于还原路径"
  },
  "symbols_units": {
    "b": "每个顶点的平均分支数",
    "d": "起点到终点的距离"
  },
  "assumptions": [
    "读者已掌握 12.2 的 DFS 与 9.3 的层序遍历",
    "读者理解 5.2 的队列与环形缓冲区"
  ],
  "word_count_actual": 3280,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch12/Sec123/",
    "分层追踪、四条路径、240 组暴力验证、性能对比、星形图空间对比均为实测",
    "练习 12.3.1/12.3.2 的 BFS 与 prev 数组已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版路径还原用「从 0 出发」的 prev 数组去查其他起点的路径，结果 0→3、1→5 全是错的（2→2 甚至显示「不可达（1 步）」自相矛盾）；已改为每个起点重新跑 BFS，并把「prev 是某个起点的 BFS 树」这个坑写进正文",
    "初版实验五用【迭代版】DFS 对比空间，实测栈峰值也是 100000（因为一次把所有邻居压栈），与「DFS 栈小」的结论矛盾；已改用【递归版】DFS（栈深度才是真正的递归深度），星形图上只有 1，并将「结论针对递归版」写进正文"
  ],
  "next": "12.4 连通分量、环检测与二分图"
}

12.3　广度优先搜索