学习顺序主线第 18 / 22 课 · 阶段 6

为什么现在学:将队列用于按层扩展,先学最直观的无权图搜索。

返回算法课程
图与搜索基础

广度优先搜索Breadth-First Search

用队列按距离一层层扩展,先处理离起点更近的节点。

40 分钟前置:队列 · 图的邻接表 · 集合

学完这一课,你应该能做到

  • 同时追踪待处理队列与已经发现的集合
  • 解释首次发现为何得到最少边数
  • 区分遍历顺序与最短路径本身

01先从一个问题出发

在每条路都走一步的迷宫里寻找最少步数。先检查一步可达的位置,再检查两步可达的位置。

一个具体的例子

无向边 0–1、0–2、1–3、2–3,从 0 开始,邻居按编号检查。

把所有一步可达的位置先放进队列

从节点 0 出发,直接邻居 1、2 都只需要一条边到达。先把它们放入队列,处理 1 时发现距离为 2 的节点 3,把 3 加在队尾;已经在前面的 2 会先于 3 被处理。

这种先进先出的安排,让距离为 d 的节点在距离为 d+1 的节点之前展开。它建立了分层,不要求节点编号本身有大小关系。页面按编号枚举邻居只是为了让演示顺序确定,不是 BFS 正确性的前提。

发现与处理要分开

visited 在这里更准确地表示『已经发现并安排入队』,不是必须已经出队处理。图中 1、2 都连接 3。处理 1 时就把 3 加入 visited,随后处理 2 时便不会重复安排 3。

本页参考函数返回访问顺序,不直接返回一条最短路径。若要输出路径,需要首次发现 neighbor 时记录 parent[neighbor]=node;若只要距离,记录 dist[neighbor]=dist[node]+1。知道工具输出了什么,才能把它用于题目。

02最直接的办法,为什么慢?

枚举所有简单路径,再选择最短的。

暴力 · 最坏 O(V!) 条路径

同一节点会通过大量不同路径被重复探索,简单路径数量可能达到阶乘级。

03一步步,推导出优化思路

1

用边数定义距离层次

无权图中,路径长度只由边数决定。

2

用队列让浅层先展开

用先进先出队列保证距离较小的节点先扩展。

3

首次发现就标记并入队

节点第一次被发现就标记并入队,避免环和重复入队。

贯穿算法的不变量

队列中的节点按距源点的最少边数非递减排列。

拿一个小输入,逐步手算

无向边 0–1、0–2、1–3、2–3,从 0 开始,邻居按编号检查。

处理动作队列(左端出队)已发现新增信息
初始化[0]{0}dist[0]=0
出队 0,发现 1、2[1,2]{0,1,2}1、2 的层数为 1
出队 1,发现 3[2,3]{0,1,2,3}3 的层数为 2
出队 2[3]不变3 已发现,不再入队
出队 3[]不变结束,顺序 0,1,2,3

3 只入队一次。层数 2 表示最少边数,不是队列当前长度,也不是节点编号。

为什么第一次发现就是最短层数

  1. 起点层数为 0。队列初始只有起点,按距离非递减排列。
  2. 从层 d 的节点发现邻居,得到一条长度 d+1 的路径;新邻居放在队尾,所有更浅的候选会先被处理。
  3. 如果邻居存在更短的路径,它应从更浅层提前被发现,与『此刻首次发现』矛盾。因此首次记录的边数最小。这个证明要求边权相同或直接只数边。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Breadth-First Search交互演示
STEP 01 / 12
0123
无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01

从节点 0 开始:入队时标记,避免重复进入队列。

bfs.py参考实现 · 当前第 4 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

queue, visited, order = deque([start]), {start}, []
起点入队时就标记,否则在无向图中邻居可能再次把起点加入队列。
node = queue.popleft()
FIFO 是层数保证的来源。改成 pop 会改变探索顺序,失去普通 BFS 的最短层数证明。
visited.add(neighbor)
首次发现时立即标记,再入队,防止不同父节点把同一邻居重复安排。
return order
返回可达节点的处理顺序。本版本不会自动访问其他连通分量,也没有保存用于恢复路径的 parent。

05复杂度,来自具体的工作量

时间复杂度
O(V+E)O(V+E)

邻接表实现中每个可达节点出队一次,每条无向边最多检查两次,总共 O(V+E)。

辅助空间
O(V)O(V)

visited、队列和输出各最多包含 V 个节点。JavaScript 用 head 下标避免 shift 的线性搬移。

拖动 n,看看增长速度

把工作量具体数出来

邻接表下每个可达节点出队一次;每条无向边最多检查两个方向。整体上界 O(V+E),实际只扫描起点可达的那部分。

visited、队列与访问顺序最多各存 V 项,额外空间 O(V)。输入邻接表本身 O(V+E),通常单独列出。

若用邻接矩阵,枚举每个节点的邻居要扫描 V 格,总时间可变为 O(V²)。算法名字相同,表示方式仍会改变成本。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

入队时标记

等到出队才标记,会让同一节点重复进入队列。

02

权重限制

边权不同的最短路一般不能直接用普通 BFS。

用反例检查前提

最少边数可能很贵

0 直接到 1 的边权为 10,另有 0→2→1 两条边、各权重 1。BFS 会优先发现只有一条边的路线,但总成本 10 大于两条边的 2。

怎样修正:普通 BFS 用于无权或等权最短路;非负不同权重的最小总代价,继续学习 Dijkstra。不要把层数直接当成耗时。

08把想法带进真实题目

合上答案,自己推一次

把访问顺序变成路径

在本课图中,若首次发现时记录父节点,parent[1]、parent[2]、parent[3] 分别是什么?如何还原 0 到 3 的一条最短路径?

需要一点提示

3 是在处理 1 时第一次发现的;沿 parent 反向追踪后再反转。

查看完整推导与答案
  1. parent[1]=0、parent[2]=0、parent[3]=1。
  2. 从 3 沿父节点得到 3→1→0,反转后是 0→1→3,共 2 条边。
  3. 0→2→3 也是最短路径,邻居顺序可能影响返回哪一条,但不影响最短长度。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01什么时候标记 visited?

02BFS 最短路适用于?

03图不连通时,从 0 开始会怎样?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。