1. 从迷宫到地图为什么你该重新认识广度优先搜索先讲一个我真实踩过的坑。早些年做某个跨平台系统的路径规划模块拿到需求第一反应是深度优先搜索——代码写得快递归一梭子下去小地图跑得飞起。结果数据量一上来地图上节点过千系统开始明显卡顿甚至在某些死胡同分支上反复横跳要等好几秒才能绕出来。后来换成广度优先搜索BFS同样场景瞬间出结果那一下才真正意识到搜索算法不是“能跑就行”选错策略性能差距是数量级的。广度优先搜索英文全称 Breadth-First Search简称 BFS是图论和算法面试里最基础也最容易被低估的算法之一。它的核心理念只能用一句大白话概括一层一层往外扩先把离起点最近的节点全部扫一遍再去更远的地方。就像水面上丢一颗石子涟漪一圈一圈向外扩散先到近岸再到远岸绝不会越过内圈直接跳到外圈。这篇内容我想面向三类读者来写刚接触算法、正在刷题找工作的应届生工作中需要用图搜索解决实际问题的开发者以及纯粹想搞懂“为什么 BFS 能求最短路径、DFS 不行”的好奇派。无论你属于哪一类读完这篇文章你不仅能在纸上画出 BFS 的完整遍历顺序还能徒手实现一套 BFS并真正理解它为什么是“最短路径问题的默认答案”。2. 图解本质一层一层剥开图的结构2.1 从一个具体例子说起假设我们有一张图节点分别是 A、B、C、D、E、F边的关系如下A 连接到 B、CB 连接到 A、D、EC 连接到 A、FD 连接到 BE 连接到 B、FF 连接到 C、E如果起点是 ABFS 的访问顺序是什么先看第一层从 A 出发A 的邻居有 B 和 C所以先访问 B、C。接着处理 B 的邻居 D、E再处理 C 的邻居 F。但注意B、C 是 A 的邻居D、E、F 是第二层节点BFS 绝不回头去处理“已经访问过”的节点所以 D、E、F 处理完之后整张图遍历结束。最终的访问顺序是A — B — C — D — E — F。为了把这个过程“看见”我强烈建议你亲自画一张图圆圈代表节点箭头或直线代表边然后把 A 放在最左边B、C 放在中间D、E、F 放在最右边。接下来用标号依次标记“第 0 层A”、“第 1 层B、C”、“第 2 层D、E、F”。你会很直观地发现BFS 的访问顺序就是按照节点距离起点的“跳数”从小到大依次访问的。2.2 队列在 BFS 中是不可替代的很多教材直接告诉你“BFS 用队列实现”但没解释为什么必须是队列。这里我把底层逻辑拆给你看。BFS 的遍历规则是先访问的节点要先扩展它的邻居。先来先服务——这不就是队列的经典语义吗用queue来保存“待扩展的节点”每次从队头取出一个节点处理再把它未访问过的邻居依次压入队尾。队列的先进先出特性天然保证了“层与层之间的先后顺序正确”。如果你试图用栈来实现 BFS那就会退化成类似 DFS 的行为——后加入的节点先扩展整个遍历顺序就错乱成深度优先了。栈不是不能用而是它表达的是“后进先出”和 BFS 的“先进先出”逻辑完全冲突。所以BFS 实现的第一要义是一定要用队列。语言无所谓C 的std::queue、Python 的collections.deque、Java 的LinkedList都可以关键是容器语义必须先进先出。个人建议在 Python 中优先使用deque因为list.pop(0)的时间复杂度是 O(n)而deque.popleft()是 O(1)这个细节在大数据量下影响极大。3. BFS 为什么能求最短路径三个关键词在说明代码之前我想先回答一个高频问题为什么同样都是搜索深度优先搜索DFS就求不出最短路径而 BFS 可以关键在于 BFS 的三个性质3.1 层级才是核心BFS 是按“层”推进的。第 1 层是与起点距离为 1 的所有节点第 2 层是与起点距离为 2 的所有节点。所以当你第一次从队列中弹出某个节点时它被弹出时所在的层级就是它到起点的最短距离前提是每条边的权重相同都是 1。说得更直白一点假设你从位置 X 出发一步能走一格BFS 先找到所有一步能到的格子再找两步能到的格子。第一个到达目标格子的路径一定是用步数最少的。这叫“首次到达即最优”是 BFS 最重要的性质。3.2 访问标记是灵魂如果没有“访问标记”visited setBFS 会陷入死循环——比如 A 的邻居是 BB 的邻居又是 A你在 B 处理时发现 A 没访问过又把它入队A 再入队处理时又把 B 入队……无限循环下去。实现中的关键就是用一个集合记录“已经访问过”的节点每当一个节点被入队就要立刻标记为已访问而不是等到出队时才标记。这里有一个非常常见的 bug很多新手是“出队时才标记已访问”。表面逻辑似乎没问题但在某些场景下会导致重复入队进而影响正确性和效率——尤其在求最短路径时重复入队可能让某个节点被多次扩展破坏“首次到达即最优”的保证。3.3 无权图的最短路径专用BFS 求最短路径的前提是路径的“代价”由节点跳数衡量且每条边权重相同。如果是带权图比如边权重分别为 2、5、1BFS 就不适用了需要用 Dijkstra 算法或 A*它们在本质上是 BFS 的加权推广。很多教材把 Dijkstra 描述成“带权版 BFS”这个类比非常准确。理解 BFS 是理解 Dijkstra 的第一步两者共享同一个“按距离从小到大扩展”的核心骨架只是 Dijkstra 用优先队列堆替换了普通队列按累计权值排序而不是按层排序。4. 从零到一BFS 的标准实现与图解代码直接上代码。下面用 Python 实现注释我会写得比较详细目的是让你能把每一行和刚才的图解对应起来。from collections import deque def bfs(graph, start): graph: 邻接表表示的图类型为 dict 例如 { A: [B, C], B: [A, D, E], ... } start: 起始节点 返回: 从 start 出发的 BFS 遍历顺序列表 if start not in graph: return [] visited set() # 记录已访问节点防止重复入队 queue deque([start]) # 使用队列先进先出 order [] # 记录访问顺序 visited.add(start) # 入队时立刻标记已访问 while queue: node queue.popleft() # 取出队头节点 order.append(node) # 记录访问顺序 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order if __name__ __main__: # 对应第 2 节中的示例图 graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] } print(bfs(graph, A)) # 输出: [A, B, C, D, E, F]4.1 逐行拆解为什么这么写第 4 行注释中的“邻接表”是图的常见存储方式。对于每个节点用列表记录它的所有邻居。这种结构的好处是查询某个节点的所有邻居时时间复杂度是 O(节点的度数)非常高效。处理大数据量图时邻接表比邻接矩阵省空间且遍历更快。第 12 行visited set()。为什么是集合而不是列表因为集合的查找是 O(1)列表的in操作是 O(n)。在节点数量很大的情况下这个差异会被无限放大。我见过有人用列表记录 visited 导致整图遍历超过 10 秒的惨案换成集合后毫秒级出结果。第 13 行queue deque([start])。队列初始化只有起点。第 16 行visited.add(start)这行非常关键。很多人会漏掉导致起点被反复入队。这里再强调一次入队时就要标记不是出队时标记。第 18-26 行循环体内的逻辑是标准的 BFS 四步出队、记录、遍历邻居、未访问则入队。这个过程对应图解里“处理当前层”和“生成下一层”的全部工作。4.2 不只是遍历序列同时记录层级如果只是输出访问顺序BFS 还谈不上多强。真正高频的需求是给定起点和终点求最短路径长度。这只需在 BFS 过程中额外记录每个节点的层级即到起点的距离。from collections import deque def bfs_shortest_distance(graph, start, target): if start target: return 0 visited {start} queue deque([(start, 0)]) # 携带层级信息 while queue: node, dist queue.popleft() for neighbor in graph[node]: if neighbor target: return dist 1 if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist 1)) return -1 # 无法到达这里的关键技巧是在队列里不仅存节点还存“节点与起点的距离”。每访问一个邻居距离就等于当前节点的距离 1。当某个邻居恰好是目标节点时直接返回dist 1这就是最短路径长度。4.3 进阶如何记录完整路径只求距离还不够很多实际场景需要输出完整路径比如从 A 到 F 经过哪些节点。做法是额外维护一个“父节点映射”from collections import deque def bfs_shortest_path(graph, start, target): if start target: return [start] visited {start} queue deque([start]) parent {start: None} while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) parent[neighbor] node # 记录前驱节点 queue.append(neighbor) if neighbor target: # 回溯路径 path [] cur target while cur is not None: path.append(cur) cur parent[cur] return path[::-1] # 反转 return [] # 无路径整个技巧的核心是每个节点被谁发现就从记录的“父节点”开始反向回溯一直走回起点。父节点映射是 BFS 求完整路径的标配理解了它你就相当于掌握了图搜索中“恢复路径”的通法——Dijkstra 和 A* 中恢复路径的思路也是这么干的。5. 实战演练从迷宫最短路径到“朋友推荐”算法不能只停留在纸上。我自己工作这几年BFS 在不少地方都用得上这里挑两个最典型的实战场景拆解。5.1 网格地图与迷宫BFS 求解最短步数假设有一个m x n的迷宫0代表可通行1代表障碍物。给定起点(0, 0)和终点(m-1, n-1)求最少需要走多少步。这是非常经典的 LeetCode 类型题目也是各类智能车、扫地机器人路径规划的简化版模型。核心思路把迷宫升维成图。网格中每个坐标都是一个节点上下左右相邻且可通行的坐标之间有一条边。BFS 从起点出发首次扩展到终点时就是最短步数。from collections import deque def shortest_steps(maze): if not maze or not maze[0]: return -1 m, n len(maze), len(maze[0]) if maze[0][0] 1 or maze[m-1][n-1] 1: return -1 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] visited {(0, 0)} queue deque([(0, 0, 0)]) # (行, 列, 当前步数) while queue: row, col, steps queue.popleft() if row m - 1 and col n - 1: return steps for dr, dc in directions: nr, nc row dr, col dc if 0 nr m and 0 nc n: if maze[nr][nc] 0 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, steps 1)) return -1这段代码最需要注意的两个细节边界检查不能省上下左右移动时必须先检查nr、nc是否落在迷宫范围内。漏掉边界检查是这类题最经典的运行时错误来源一出现就是数组越界。方向数组的写法directions列表顺序不影响正确性只影响同层节点的扩展顺序。如果你希望搜索时“优先向上”把(-1, 0)放在第一个即可这个细节在需要稳定输出顺序的调试场景中非常有用。5.2 “你可能认识的人”社交网络中的 BFS社交平台的好友推荐本质上就是一个图搜索问题。如果把每个人看成一个节点好友关系看成一条边那“你可能认识的人”就是在二度人脉、三度人脉里找符合条件的人。BFS 按层级扩展的天性正好适合推荐“距离你两跳、但还不认识”的人。一个简化版本给定社交关系图找出所有与起点距离为 2 的人不包括起点直接认识的。from collections import deque def recommend_friends(graph, start, depth2): result [] visited {start} queue deque([(start, 0)]) while queue: person, level queue.popleft() if level depth: result.append(person) continue if level depth: break for neighbor in graph[person]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, level 1)) return result这个场景如果对于某些平台是“发现页”的雏形那对你做推荐系统、人际关系分析、影响力传播模拟都有参考价值。实际业务中会在此基础上加上“排除已有好友”“按共同好友数排序”等规则但骨架不变BFS 负责找出候选集。6. 常见问题与排查技巧实录6.1 死循环为什么我的 BFS 停不下来症状程序运行很久不结束或者内存爆炸。排查思路检查visited集合。最常见的两个原因忘记将起点加入visited导致起点被反复入队。图中有环但在遍历邻居时没有正确判断“该邻居是否已访问”把已经处理过的节点再次入队。经验法则每入队一个节点就必须立即加入 visited。如果两次入队的节点集合有重叠基本可以判定标记逻辑有问题。6.2 结果正确但性能很差输入大图直接卡死症状小图秒过大图卡到怀疑人生。排查重点容器选型。检查是否在用list当队列用比如queue.append(...)后node queue.pop(0)。这个pop(0)每次都是 O(n)图为 1 万节点时就会明显卡顿。换成collections.deque之后性能立刻恢复。另外检查visited是set还是list。if neighbor not in visited对list是 O(n) 查找对set是 O(1)。这是大图卡顿的另一大来源。6.3 最短路径貌似不准忽略“无权图”的前提症状在有边权的图中用 BFS 求最短路径结果不是最优。原因很简单BFS 只适用于每条边代价相同的图。当地图里不同路径消耗不同体力、不同时间时BFS 就不再适用需要换成 Dijkstra 或 A*。这是算法选型的问题不是实现 bug。我在项目里就吃过这个亏——游戏地图中不同地形移动消耗不同一开始图省事用 BFS结果绕远路后来换成 Dijkstra 才真正解决问题。6.4 队列里存 tuple 时的常见错误在记录层级的 BFS 中队列元组写法queue.append((node, dist 1))比较常见。注意不要写成queue.append(node, dist 1)这会把两个参数分别传给append直接报TypeError。这类问题多在培训学员身上出现一看报错信息就能定位。7. 图解算法的理解加速器画图第一代码第二最后想分享一个我个人带项目团队时的经验给新人讲 BFS我不让他们先看代码而是让他们先画图。准备好一张网格纸和一盒彩色笔从起点开始把第 0 层涂一种颜色第 1 层涂另一种颜色第 2 层再换一种。画完一张图队列、visited、层级、最短路径这四件事就全部明白了。为什么画图这么有效因为 BFS 的每一步操作都是“看得见”的。队列里的元素就是“已经发现但还没扩展完”的节点visited 里的元素就是“已经涂过色的节点”层级就是“涂色批次”。代码只是把这三个可视化概念翻译成了机器能执行的动作。如果你要做笔记别只抄代码。我建议你画三层结构的快照第 1 行画队列状态第 2 行画 visited 集合状态第 3 行画正在扩展的节点与它的邻居对着快照一行行比对代码你会发现 BFS 的逻辑闭环一下子就通了。我在给团队做内部分享时用过这种教学法效果比直接“刷题”好很多——大家不是背模板而是真正理解为什么队列先进先出为什么入队即标记。8. BFS 之后下一站 Dijkstra 与 A*如果你已经能把 BFS 徒手写出来、能在图上画出层级接下来值得考虑两条延伸路线第一条把“队列”换成“优先队列”。Dijkstra 算法本质上沿用了 BFS 的“按距离从小到大扩展”骨架但把普通队列换成按累计距离排序的优先队列就能处理带权图。理解了 BFS再看 Dijkstra 会轻松很多。第二条加入“启发式评估”。A* 算法在 Dijkstra 基础上增加一个估算函数优先扩展“离终点更近”的节点。日常导航、游戏寻路都大量使用 A*。它的推导起点依然是 BFS 的层级思想。我个人做算法速成带教时通常会按“BFS → Dijkstra → A*”的顺序推进。这个顺序不是随意选的而是因为你每往上走一步都能在 BFS 的骨架里找到对应结构的升级点——队列变优先队列、无启发式变成有启发式。BFS 是一栋大楼的地基地基打不牢上层建筑再花哨也站不住。所以如果你今天只记住一个点那就记住这句BFS 队列 层级扩展 首次到达即最优。只要把你的问题抽象成“无权图上的最短路径”BFS 就该是你脑子里最先弹出的答案。至于画图、标签、代码实践这些都是为了让这个答案真正长在你自己身上。 
长河君 · 2026/10/16 20:05:38 · 阅读 1.2k 广度优先搜索BFS核心解析：队列原理与最短路径实战
1. 从迷宫到地图为什么你该重新认识广度优先搜索先讲一个我真实踩过的坑。早些年做某个跨平台系统的路径规划模块拿到需求第一反应是深度优先搜索——代码写得快递归一梭子下去小地图跑得飞起。结果数据量一上来地图上节点过千系统开始明显卡顿甚至在某些死胡同分支上反复横跳要等好几秒才能绕出来。后来换成广度优先搜索BFS同样场景瞬间出结果那一下才真正意识到搜索算法不是“能跑就行”选错策略性能差距是数量级的。广度优先搜索英文全称 Breadth-First Search简称 BFS是图论和算法面试里最基础也最容易被低估的算法之一。它的核心理念只能用一句大白话概括一层一层往外扩先把离起点最近的节点全部扫一遍再去更远的地方。就像水面上丢一颗石子涟漪一圈一圈向外扩散先到近岸再到远岸绝不会越过内圈直接跳到外圈。这篇内容我想面向三类读者来写刚接触算法、正在刷题找工作的应届生工作中需要用图搜索解决实际问题的开发者以及纯粹想搞懂“为什么 BFS 能求最短路径、DFS 不行”的好奇派。无论你属于哪一类读完这篇文章你不仅能在纸上画出 BFS 的完整遍历顺序还能徒手实现一套 BFS并真正理解它为什么是“最短路径问题的默认答案”。2. 图解本质一层一层剥开图的结构2.1 从一个具体例子说起假设我们有一张图节点分别是 A、B、C、D、E、F边的关系如下A 连接到 B、CB 连接到 A、D、EC 连接到 A、FD 连接到 BE 连接到 B、FF 连接到 C、E如果起点是 ABFS 的访问顺序是什么先看第一层从 A 出发A 的邻居有 B 和 C所以先访问 B、C。接着处理 B 的邻居 D、E再处理 C 的邻居 F。但注意B、C 是 A 的邻居D、E、F 是第二层节点BFS 绝不回头去处理“已经访问过”的节点所以 D、E、F 处理完之后整张图遍历结束。最终的访问顺序是A — B — C — D — E — F。为了把这个过程“看见”我强烈建议你亲自画一张图圆圈代表节点箭头或直线代表边然后把 A 放在最左边B、C 放在中间D、E、F 放在最右边。接下来用标号依次标记“第 0 层A”、“第 1 层B、C”、“第 2 层D、E、F”。你会很直观地发现BFS 的访问顺序就是按照节点距离起点的“跳数”从小到大依次访问的。2.2 队列在 BFS 中是不可替代的很多教材直接告诉你“BFS 用队列实现”但没解释为什么必须是队列。这里我把底层逻辑拆给你看。BFS 的遍历规则是先访问的节点要先扩展它的邻居。先来先服务——这不就是队列的经典语义吗用queue来保存“待扩展的节点”每次从队头取出一个节点处理再把它未访问过的邻居依次压入队尾。队列的先进先出特性天然保证了“层与层之间的先后顺序正确”。如果你试图用栈来实现 BFS那就会退化成类似 DFS 的行为——后加入的节点先扩展整个遍历顺序就错乱成深度优先了。栈不是不能用而是它表达的是“后进先出”和 BFS 的“先进先出”逻辑完全冲突。所以BFS 实现的第一要义是一定要用队列。语言无所谓C 的std::queue、Python 的collections.deque、Java 的LinkedList都可以关键是容器语义必须先进先出。个人建议在 Python 中优先使用deque因为list.pop(0)的时间复杂度是 O(n)而deque.popleft()是 O(1)这个细节在大数据量下影响极大。3. BFS 为什么能求最短路径三个关键词在说明代码之前我想先回答一个高频问题为什么同样都是搜索深度优先搜索DFS就求不出最短路径而 BFS 可以关键在于 BFS 的三个性质3.1 层级才是核心BFS 是按“层”推进的。第 1 层是与起点距离为 1 的所有节点第 2 层是与起点距离为 2 的所有节点。所以当你第一次从队列中弹出某个节点时它被弹出时所在的层级就是它到起点的最短距离前提是每条边的权重相同都是 1。说得更直白一点假设你从位置 X 出发一步能走一格BFS 先找到所有一步能到的格子再找两步能到的格子。第一个到达目标格子的路径一定是用步数最少的。这叫“首次到达即最优”是 BFS 最重要的性质。3.2 访问标记是灵魂如果没有“访问标记”visited setBFS 会陷入死循环——比如 A 的邻居是 BB 的邻居又是 A你在 B 处理时发现 A 没访问过又把它入队A 再入队处理时又把 B 入队……无限循环下去。实现中的关键就是用一个集合记录“已经访问过”的节点每当一个节点被入队就要立刻标记为已访问而不是等到出队时才标记。这里有一个非常常见的 bug很多新手是“出队时才标记已访问”。表面逻辑似乎没问题但在某些场景下会导致重复入队进而影响正确性和效率——尤其在求最短路径时重复入队可能让某个节点被多次扩展破坏“首次到达即最优”的保证。3.3 无权图的最短路径专用BFS 求最短路径的前提是路径的“代价”由节点跳数衡量且每条边权重相同。如果是带权图比如边权重分别为 2、5、1BFS 就不适用了需要用 Dijkstra 算法或 A*它们在本质上是 BFS 的加权推广。很多教材把 Dijkstra 描述成“带权版 BFS”这个类比非常准确。理解 BFS 是理解 Dijkstra 的第一步两者共享同一个“按距离从小到大扩展”的核心骨架只是 Dijkstra 用优先队列堆替换了普通队列按累计权值排序而不是按层排序。4. 从零到一BFS 的标准实现与图解代码直接上代码。下面用 Python 实现注释我会写得比较详细目的是让你能把每一行和刚才的图解对应起来。from collections import deque def bfs(graph, start): graph: 邻接表表示的图类型为 dict 例如 { A: [B, C], B: [A, D, E], ... } start: 起始节点 返回: 从 start 出发的 BFS 遍历顺序列表 if start not in graph: return [] visited set() # 记录已访问节点防止重复入队 queue deque([start]) # 使用队列先进先出 order [] # 记录访问顺序 visited.add(start) # 入队时立刻标记已访问 while queue: node queue.popleft() # 取出队头节点 order.append(node) # 记录访问顺序 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order if __name__ __main__: # 对应第 2 节中的示例图 graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] } print(bfs(graph, A)) # 输出: [A, B, C, D, E, F]4.1 逐行拆解为什么这么写第 4 行注释中的“邻接表”是图的常见存储方式。对于每个节点用列表记录它的所有邻居。这种结构的好处是查询某个节点的所有邻居时时间复杂度是 O(节点的度数)非常高效。处理大数据量图时邻接表比邻接矩阵省空间且遍历更快。第 12 行visited set()。为什么是集合而不是列表因为集合的查找是 O(1)列表的in操作是 O(n)。在节点数量很大的情况下这个差异会被无限放大。我见过有人用列表记录 visited 导致整图遍历超过 10 秒的惨案换成集合后毫秒级出结果。第 13 行queue deque([start])。队列初始化只有起点。第 16 行visited.add(start)这行非常关键。很多人会漏掉导致起点被反复入队。这里再强调一次入队时就要标记不是出队时标记。第 18-26 行循环体内的逻辑是标准的 BFS 四步出队、记录、遍历邻居、未访问则入队。这个过程对应图解里“处理当前层”和“生成下一层”的全部工作。4.2 不只是遍历序列同时记录层级如果只是输出访问顺序BFS 还谈不上多强。真正高频的需求是给定起点和终点求最短路径长度。这只需在 BFS 过程中额外记录每个节点的层级即到起点的距离。from collections import deque def bfs_shortest_distance(graph, start, target): if start target: return 0 visited {start} queue deque([(start, 0)]) # 携带层级信息 while queue: node, dist queue.popleft() for neighbor in graph[node]: if neighbor target: return dist 1 if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist 1)) return -1 # 无法到达这里的关键技巧是在队列里不仅存节点还存“节点与起点的距离”。每访问一个邻居距离就等于当前节点的距离 1。当某个邻居恰好是目标节点时直接返回dist 1这就是最短路径长度。4.3 进阶如何记录完整路径只求距离还不够很多实际场景需要输出完整路径比如从 A 到 F 经过哪些节点。做法是额外维护一个“父节点映射”from collections import deque def bfs_shortest_path(graph, start, target): if start target: return [start] visited {start} queue deque([start]) parent {start: None} while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) parent[neighbor] node # 记录前驱节点 queue.append(neighbor) if neighbor target: # 回溯路径 path [] cur target while cur is not None: path.append(cur) cur parent[cur] return path[::-1] # 反转 return [] # 无路径整个技巧的核心是每个节点被谁发现就从记录的“父节点”开始反向回溯一直走回起点。父节点映射是 BFS 求完整路径的标配理解了它你就相当于掌握了图搜索中“恢复路径”的通法——Dijkstra 和 A* 中恢复路径的思路也是这么干的。5. 实战演练从迷宫最短路径到“朋友推荐”算法不能只停留在纸上。我自己工作这几年BFS 在不少地方都用得上这里挑两个最典型的实战场景拆解。5.1 网格地图与迷宫BFS 求解最短步数假设有一个m x n的迷宫0代表可通行1代表障碍物。给定起点(0, 0)和终点(m-1, n-1)求最少需要走多少步。这是非常经典的 LeetCode 类型题目也是各类智能车、扫地机器人路径规划的简化版模型。核心思路把迷宫升维成图。网格中每个坐标都是一个节点上下左右相邻且可通行的坐标之间有一条边。BFS 从起点出发首次扩展到终点时就是最短步数。from collections import deque def shortest_steps(maze): if not maze or not maze[0]: return -1 m, n len(maze), len(maze[0]) if maze[0][0] 1 or maze[m-1][n-1] 1: return -1 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] visited {(0, 0)} queue deque([(0, 0, 0)]) # (行, 列, 当前步数) while queue: row, col, steps queue.popleft() if row m - 1 and col n - 1: return steps for dr, dc in directions: nr, nc row dr, col dc if 0 nr m and 0 nc n: if maze[nr][nc] 0 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, steps 1)) return -1这段代码最需要注意的两个细节边界检查不能省上下左右移动时必须先检查nr、nc是否落在迷宫范围内。漏掉边界检查是这类题最经典的运行时错误来源一出现就是数组越界。方向数组的写法directions列表顺序不影响正确性只影响同层节点的扩展顺序。如果你希望搜索时“优先向上”把(-1, 0)放在第一个即可这个细节在需要稳定输出顺序的调试场景中非常有用。5.2 “你可能认识的人”社交网络中的 BFS社交平台的好友推荐本质上就是一个图搜索问题。如果把每个人看成一个节点好友关系看成一条边那“你可能认识的人”就是在二度人脉、三度人脉里找符合条件的人。BFS 按层级扩展的天性正好适合推荐“距离你两跳、但还不认识”的人。一个简化版本给定社交关系图找出所有与起点距离为 2 的人不包括起点直接认识的。from collections import deque def recommend_friends(graph, start, depth2): result [] visited {start} queue deque([(start, 0)]) while queue: person, level queue.popleft() if level depth: result.append(person) continue if level depth: break for neighbor in graph[person]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, level 1)) return result这个场景如果对于某些平台是“发现页”的雏形那对你做推荐系统、人际关系分析、影响力传播模拟都有参考价值。实际业务中会在此基础上加上“排除已有好友”“按共同好友数排序”等规则但骨架不变BFS 负责找出候选集。6. 常见问题与排查技巧实录6.1 死循环为什么我的 BFS 停不下来症状程序运行很久不结束或者内存爆炸。排查思路检查visited集合。最常见的两个原因忘记将起点加入visited导致起点被反复入队。图中有环但在遍历邻居时没有正确判断“该邻居是否已访问”把已经处理过的节点再次入队。经验法则每入队一个节点就必须立即加入 visited。如果两次入队的节点集合有重叠基本可以判定标记逻辑有问题。6.2 结果正确但性能很差输入大图直接卡死症状小图秒过大图卡到怀疑人生。排查重点容器选型。检查是否在用list当队列用比如queue.append(...)后node queue.pop(0)。这个pop(0)每次都是 O(n)图为 1 万节点时就会明显卡顿。换成collections.deque之后性能立刻恢复。另外检查visited是set还是list。if neighbor not in visited对list是 O(n) 查找对set是 O(1)。这是大图卡顿的另一大来源。6.3 最短路径貌似不准忽略“无权图”的前提症状在有边权的图中用 BFS 求最短路径结果不是最优。原因很简单BFS 只适用于每条边代价相同的图。当地图里不同路径消耗不同体力、不同时间时BFS 就不再适用需要换成 Dijkstra 或 A*。这是算法选型的问题不是实现 bug。我在项目里就吃过这个亏——游戏地图中不同地形移动消耗不同一开始图省事用 BFS结果绕远路后来换成 Dijkstra 才真正解决问题。6.4 队列里存 tuple 时的常见错误在记录层级的 BFS 中队列元组写法queue.append((node, dist 1))比较常见。注意不要写成queue.append(node, dist 1)这会把两个参数分别传给append直接报TypeError。这类问题多在培训学员身上出现一看报错信息就能定位。7. 图解算法的理解加速器画图第一代码第二最后想分享一个我个人带项目团队时的经验给新人讲 BFS我不让他们先看代码而是让他们先画图。准备好一张网格纸和一盒彩色笔从起点开始把第 0 层涂一种颜色第 1 层涂另一种颜色第 2 层再换一种。画完一张图队列、visited、层级、最短路径这四件事就全部明白了。为什么画图这么有效因为 BFS 的每一步操作都是“看得见”的。队列里的元素就是“已经发现但还没扩展完”的节点visited 里的元素就是“已经涂过色的节点”层级就是“涂色批次”。代码只是把这三个可视化概念翻译成了机器能执行的动作。如果你要做笔记别只抄代码。我建议你画三层结构的快照第 1 行画队列状态第 2 行画 visited 集合状态第 3 行画正在扩展的节点与它的邻居对着快照一行行比对代码你会发现 BFS 的逻辑闭环一下子就通了。我在给团队做内部分享时用过这种教学法效果比直接“刷题”好很多——大家不是背模板而是真正理解为什么队列先进先出为什么入队即标记。8. BFS 之后下一站 Dijkstra 与 A*如果你已经能把 BFS 徒手写出来、能在图上画出层级接下来值得考虑两条延伸路线第一条把“队列”换成“优先队列”。Dijkstra 算法本质上沿用了 BFS 的“按距离从小到大扩展”骨架但把普通队列换成按累计距离排序的优先队列就能处理带权图。理解了 BFS再看 Dijkstra 会轻松很多。第二条加入“启发式评估”。A* 算法在 Dijkstra 基础上增加一个估算函数优先扩展“离终点更近”的节点。日常导航、游戏寻路都大量使用 A*。它的推导起点依然是 BFS 的层级思想。我个人做算法速成带教时通常会按“BFS → Dijkstra → A*”的顺序推进。这个顺序不是随意选的而是因为你每往上走一步都能在 BFS 的骨架里找到对应结构的升级点——队列变优先队列、无启发式变成有启发式。BFS 是一栋大楼的地基地基打不牢上层建筑再花哨也站不住。所以如果你今天只记住一个点那就记住这句BFS 队列 层级扩展 首次到达即最优。只要把你的问题抽象成“无权图上的最短路径”BFS 就该是你脑子里最先弹出的答案。至于画图、标签、代码实践这些都是为了让这个答案真正长在你自己身上。