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最直接的办法,为什么慢?
枚举所有简单路径,再选择最短的。
同一节点会通过大量不同路径被重复探索,简单路径数量可能达到阶乘级。
03一步步,推导出优化思路
用边数定义距离层次
无权图中,路径长度只由边数决定。
用队列让浅层先展开
用先进先出队列保证距离较小的节点先扩展。
首次发现就标记并入队
节点第一次被发现就标记并入队,避免环和重复入队。
队列中的节点按距源点的最少边数非递减排列。
拿一个小输入,逐步手算
无向边 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 表示最少边数,不是队列当前长度,也不是节点编号。
为什么第一次发现就是最短层数
- 起点层数为 0。队列初始只有起点,按距离非递减排列。
- 从层 d 的节点发现邻居,得到一条长度 d+1 的路径;新邻居放在队尾,所有更浅的候选会先被处理。
- 如果邻居存在更短的路径,它应从更浅层提前被发现,与『此刻首次发现』矛盾。因此首次记录的边数最小。这个证明要求边权相同或直接只数边。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
从节点 0 开始:入队时标记,避免重复进入队列。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
queue, visited, order = deque([start]), {start}, []- 起点入队时就标记,否则在无向图中邻居可能再次把起点加入队列。
node = queue.popleft()- FIFO 是层数保证的来源。改成 pop 会改变探索顺序,失去普通 BFS 的最短层数证明。
visited.add(neighbor)- 首次发现时立即标记,再入队,防止不同父节点把同一邻居重复安排。
return order- 返回可达节点的处理顺序。本版本不会自动访问其他连通分量,也没有保存用于恢复路径的 parent。
05复杂度,来自具体的工作量
邻接表实现中每个可达节点出队一次,每条无向边最多检查两次,总共 O(V+E)。
visited、队列和输出各最多包含 V 个节点。JavaScript 用 head 下标避免 shift 的线性搬移。
把工作量具体数出来
邻接表下每个可达节点出队一次;每条无向边最多检查两个方向。整体上界 O(V+E),实际只扫描起点可达的那部分。
visited、队列与访问顺序最多各存 V 项,额外空间 O(V)。输入邻接表本身 O(V+E),通常单独列出。
若用邻接矩阵,枚举每个节点的邻居要扫描 V 格,总时间可变为 O(V²)。算法名字相同,表示方式仍会改变成本。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
入队时标记
等到出队才标记,会让同一节点重复进入队列。
权重限制
边权不同的最短路一般不能直接用普通 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 反向追踪后再反转。
查看完整推导与答案
- parent[1]=0、parent[2]=0、parent[3]=1。
- 从 3 沿父节点得到 3→1→0,反转后是 0→1→3,共 2 条边。
- 0→2→3 也是最短路径,邻居顺序可能影响返回哪一条,但不影响最短长度。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01什么时候标记 visited?
02BFS 最短路适用于?
03图不连通时,从 0 开始会怎样?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。