简介面向算法初学者与力扣刷题者这份BFS源码包不仅讲解广度优先搜索的概念与适用场景还通过走迷宫问题展示最短路径的求解过程并补充了网络路由、图形学渲染、人工智能八数码问题等典型应用。包内共四个文件包括可运行的Python示例脚本、算法要点txt说明、PNG示意图及inscode项目配置压缩包仅114KB结构清晰便于快速浏览或直接运行。目前已有二百六十九人浏览学习。内容还覆盖Word Ladder和Word Break II两道力扣例题通过单词转换与句子拆分场景展示BFS的解题思路同时给出时间复杂度O(V)、空间复杂度O(E)分析帮助读者快速评估算法性能。配合源码中的注释与流程图可以理解队列在逐层遍历中的作用、访问标记如何避免重复搜索将这些要点迁移到其他图论问题中。1. BFS 到底是什么从“逐层扩散”看懂它的适用场景假设你在一个网格地图上从起点出发走到终点每一步只能上下左右移动一格。在没有障碍的图上闭着眼睛也知道答案横着走几步、竖着走几步距离就出来了。但如果地图里有墙、有岔路、有多个终点你凭什么保证第一次碰到目标时的路径就是最短的BFS广度优先搜索Breadth-First Search就是为这类“无权图上的最短路径”问题准备的。它的核心动作只有一句话从起点开始一圈一圈往外扩散先检查离起点最近的邻居再检查邻居的邻居逐层推进直到碰到目标或者全部搜完。这套“逐层扩散”的机制决定了 BFS 和 DFS深度优先搜索完全不同的性格。DFS 是“一条路走到黑撞墙再回头”适合找可行解、枚举组合BFS 则靠“同层先比、层层递进”的次序保证第一次命中就是最优步数。真正让 BFS 比其他搜索算法更值得优先掌握的原因在于它不依赖启发式信息不需要对数据做额外假设能用一张图、一个队列、一个标记数组就解决大批最短路径、连通性问题。对后端开发、嵌入式调试、算法竞赛入门以及做路径规划的工程师来说BFS 都是“先写对再优化”的默认第一版方案。但 BFS 也是“看起来简单写起来翻车”的重灾区。队列是先进先出但放在谁进队列、谁先出队、什么时候算访问过、网格边界怎么判四五个变量组合起来写法千奇百怪正确率参差不齐。这篇笔记围绕一套可复现的 BFS 源码实现展开从数据结构选型到参数设置再到真实项目里常见的踩坑点把 BFS 从“直觉层面”拉到“代码层面”。2. BFS 的核心机制队列、visited 与三个关键时机2.1 队列为什么是 BFS 的骨骼BFS 的展开顺序是“先来的先处理”这正好是先进先出FIFO队列的特性。每次从队首取出一个节点把它所有未访问的邻居依次从队尾入队下一轮从队首弹出的就一定是上一轮入队的邻居。这样一轮一轮往外剥就形成了“层次”概念。队列里装的节点有一个隐含约束同一时刻队列中相邻的节点离起点的距离要么相等、要么差 1。这一点是 BFS 正确性的基础。用栈DFS替换队列后展开顺序变成“后来者先处理”层次信息立刻丢失第一次命中目标就不再保证最短路径。选择队列时要注意的是元素粒度。常见做法是直接用标准库的queue.Queue但更推荐collections.deque。deque的popleft()是 O(1) 的而list.pop(0)是 O(n) 的在网格 500×500 规模的搜索中这两者的耗时差距是数量级差异不是常数差异。C 里直接用queue容器即可但是注意只保持一个队列实例不要为每个节点新建队列对象。2.2 visited 的标记时机入队时标记还是出队时标记这可能是 BFS 实现里最多人搞错的细节。理论上两种做法都能让搜索完成但性能与重复入队数量完全不同。入队时标记推荐判断邻居合法后立即写入visited保证一个节点只入队一次队列长度为 O(节点数)不会出现重复判断。出队时标记每个节点可能在入队前被多个邻居发现导致同一节点多次入队虽然最终结果正确但无谓增大了队列压力还可能让复杂状态搜索卡死。实际项目里我统一用“入队时标记”作为默认习惯。如果换用出队时标记必须做好一个节点被多次入队的心理准备在状态对象里不设防重那么内存消耗可能翻几倍到几十倍。对八数码这类状态搜索问题用出队时标记基本等于把内存预算烧光。2.3 轮次划分为什么第一次命中就是最短路径要证明“第一次碰到目标就是最短”关键在于 BFS 的展开顺序完全按距离分层。距离为 k 的节点一定在距离为 k1 的节点之前被访问。假设从起点到终点有一条长度为 L 的最短路径BFS 会先从起点出发依次访问距离为 1 的节点、距离为 2 的节点……当展开到某一层时路径上的第 L 个节点被访问终点必然在这一层被检查到而任何更短的路径如果存在会在更早的层次被命中。这个性质依赖两个前提每个节点只被访问一次visited 正确边的权值相同即无权图。如果边的权重不同比如地图上有泥地消耗 2 点体力、平路消耗 1 点那么“步数最少”不等于“消耗最少”BFS 的第一次命中就不是最优解这时候需要换成 Dijkstra 或 A*。理解轮次划分还有一个实际价值当你需要记录每个节点的最短距离时不需要在节点结构体里存depth字段可以直接维护一个dist[节点]数组在“发现新节点”时用dist[新节点] dist[当前节点] 1赋值。这样既能保证正确性又方便回溯路径。3. 源码里的 BFS 模板单源、网格、邻接表三种写法与参数说明这章对应“[项目源码]”的核心部分。我不会只给一个抽象骨架而是给三个能直接跑通的完整实现片段每个都标注参数含义与改动方式。源码仓库里最常被提问的也是这三个变体单源最短路模板、网格四方向搜索、多源并行 BFS。3.1 单源无权图 BFS邻接表写法from collections import deque def bfs_shortest_path(graph, start, target): # graph: dict, 邻接表, key 为节点编号, value 为邻居列表 # start: 起点编号 # target: 目标节点编号, 不存在时返回 -1 if start target: return 0 dist {} dist[start] 0 q deque([start]) while q: cur q.popleft() for nxt in graph.get(cur, []): if nxt not in dist: # 未被访问过 dist[nxt] dist[cur] 1 if nxt target: return dist[nxt] # 第一次命中即最短 q.append(nxt) return -1逻辑说明dist同时充当 visited 与距离记录两个角色比用两个独立结构更简洁也避免了“标记了但没存距离”的问题。graph.get(cur, [])防止越界 key 报错。start target的提前返回是很多人容易漏掉的边界如果不处理循环会从起点扯到邻居白搜索一整轮。参数说明如果图节点编号是连续整数 0..n-1dist可换成数组[-1] * n用-1表示未访问内存更小、访问更快。如果图是稀疏图且节点数量极大用哈希表的dist更安全。返回值 -1 表示不可达这是一种约定实际使用时最好调用方自己定义不要在函数内部硬编码为业务上的非法值。3.2 网格四方向 BFS坐标与方向数组from collections import deque def bfs_grid(grid, start, target): # grid: List[List[int]], 0 可走, 1 障碍 # start: (r, c), target: (r, c) rows, cols len(grid), len(grid[0]) if grid[start[0]][start[1]] 1 or grid[target[0]][target[1]] 1: return -1 if start target: return 0 dist [[-1] * cols for _ in range(rows)] dist[start[0]][start[1]] 0 q deque([start]) # 方向数组: 上, 下, 左, 右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: r, c q.popleft() for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 0 and dist[nr][nc] -1: dist[nr][nc] dist[r][c] 1 if (nr, nc) target: return dist[nr][nc] q.append((nr, nc)) return -1逻辑说明dist初始化为 -1既标记未访问又存放最短步数空格子走过后不再入队。方向数组写成独立的directions列表比四段重复代码清晰得多。边界检查写在坐标更新之后不要写成if 0 r dr rows这种把三件事挤在一行的写法排错时你会感谢自己。参数说明方向数组的顺序不影响最短路径正确性但影响同层节点展开顺序如果后续要输出路径方向顺序会影响路径偏好。有些题目规定“按字典序输出路径”这时方向数组必须按特定顺序如下、左、右、上排列。另外如果网格中还有传送门、加速带等特殊格子就需要把grid[nr][nc] 0的判定改成可通行标志检查并且把“扩展一步”改成“按规则跳转”。3.3 多源 BFS把多个起点一起塞进队列from collections import deque def bfs_multi_source(grid, sources): # grid: List[List[int]], 0 为空地, 1 为障碍 # sources: List[(r, c)] 多个起点, 求所有空地到最近起点的距离 rows, cols len(grid), len(grid[0]) dist [[-1] * cols for _ in range(rows)] q deque() for r, c in sources: if grid[r][c] 0: dist[r][c] 0 q.append((r, c)) directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: r, c q.popleft() for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 0 and dist[nr][nc] -1: dist[nr][nc] dist[r][c] 1 q.append((nr, nc)) return dist逻辑说明多源 BFS 的原理是“多个起点同时入队同步扩散”等价于在虚拟起点加一个权为 0 的边连接所有实际起点。这样每个格子的dist值天然等于它到最近起点的距离不用为每个起点各搜索一次再取最小值时间从 O(k×V) 降为 O(V)。参数说明如果起点坐标可能落在障碍上要像上面这样先判断grid[r][c] 0再初始化。如果起点集合特别大可以把sources转成集合避免重复入队。这个模板在“多点火灾蔓延模拟”“多个配送中心覆盖半径”场景中直接用返回的dist矩阵就是最终答案。4. 状态搜索与图搜索BFS 能套多远4.1 状态空间搜索八数码与字符串变换BFS 不只适用于图或网格还适用于“状态”之间的最小步数变换。把每一种局面看作一个节点能在一个动作内互相转换的局面之间连边问题就变成“从初始状态到目标状态的最短路径”。代码里唯一的变化是“邻居扩展”方式不再是方向数组加坐标加减而是枚举所有合法动作产出新状态。比如字符串变换问题里动作是“把某个位置的字符替换为另一个字符”那么每次扩展时遍历所有位置和所有可替换字符产出的新字符串就是邻居。from collections import deque def bfs_state(start, target, actions): # start: 初始状态 # target: 目标状态 # actions: 函数列表, 每个函数输入状态输出邻居状态列表 if start target: return 0 q deque([start]) visited {start: 0} while q: cur q.popleft() for nxt in actions(cur): if nxt not in visited: visited[nxt] visited[cur] 1 if nxt target: return visited[nxt] q.append(nxt) return -1参数说明visited这里用字典键是状态本身。如果状态可以编码成整数或字符串能够大幅提升哈希速度。对字符串状态Python 的字符串哈希自带缓存性能可接受如果状态是一个多维数组强烈建议转成元组再存入字典否则列表不可哈希会直接报错。这一点在“状态搜索”里是最高频的翻车点。4.2 最小生成树与连通性检查BFS 的邻域应用除了求最短路径BFS 的遍历能力同样适用于连通块统计。例如一个二值图像中有多少个连通区域、哪些像素属于同一个连通区域这类问题用 BFS 逐点扩散即可并且天然不会递归爆栈比 DFS 更稳。在嵌入式环境、内存受限环境中BFS 的显式队列比 DFS 的调用栈更容易控制内存上限。另一个邻域是拓扑排序的“逆用”判断图中是否存在环。BFS 从所有入度为 0 的节点开始剥离如果最终剥离节点数量等于总节点数则无环否则有环。这和普通的路径搜索长得完全不一样但底层引擎还是那套队列加标记。4.3 BFS 的适用边界什么时候该换算法BFS 有两大硬伤一是只适用无权图带权图要用 Dijkstra 或 A*二是搜索空间爆炸当状态数达到千万级以上BFS 的空间消耗会超过内存容忍度。实体项目中如果你发现队列节点的visited集合动辄上亿就需要转向双向 BFS 或 A* 这类带启发的搜索。另一个容易被忽略的边界是“边的数量远大于节点数量”的稠密图。BFS 虽然时间复杂度是 O(VE)但在稠密图里 E 接近 V²实际耗时极长。这时候要优先检查问题的结构能不能压缩比如网格图可不可以改成跳点搜索邻接表能不能用位运算批量扩展。5. BFS 避坑指南五个高频翻车点与排查方法5.1 起点等于终点时没有提前返回现象输入起点和终点是同一个坐标程序没有立刻返回 0而是绕了一大圈最后才返回一个很大的步数甚至死循环。原因很多实现只在队列弹出节点时判断是否等于终点起点入队后如果不提前处理要等它附近一圈全部入队才返回。解决在函数最开始显式判断start target同时检查起点和终点是否为合法可通行节点。这一类逻辑经常在“从自己所在位置出发找最近商店”的需求里复现。5.2 visited 放在出队时标记导致重复入队现象运行结果正确但队列长度异常膨胀数据规模稍大就内存溢出。原因出队时标记意味着一个节点可能被多个邻居各自入队一次在网格搜索里达到同一节点的路径常有几十条重复入队数量随之爆炸。解决统一改成入队时标记。排查方法很简单在q.append(nxt)前打印dist[nxt]如果发现同一个节点被赋值多次就是标记时机错了。5.3 dist 数组初始化为 0 与“未访问”混淆现象网格里起点是 0周围空地本来应该初始化为不可达结果输出距离时 0 出现在很多不该出现的位置。原因如果dist数组用 0 表示未访问起点初始也为 0那“未访问”和“起点”变成同一个语义扩展时无法区分。解决用 -1 表示未访问起点的 0 是真实距离。如果想省内存用 0 初始化就必须再维护一个独立的 visited 布尔数组但代码会多一层不推荐。5.4 网格边界判断少写一边现象搜索过程中索引越界报错或者地图边缘的格子被异常跳过。原因0 nr rows and 0 nc cols四个条件少写一个比如只判下界不判上界或只判行不判列。解决方向数组的每个分量都必须做完整边界判断。更稳的写法是先把nr, nc算好再单独写一个is_valid函数统一判断这样可以在这个函数里集中处理障碍、边界、访问标记。5.5 队列中状态对象不可哈希现象代码在nxt not in visited这一行直接抛TypeError: unhashable type: list。原因用列表表示状态列表本身不可哈希不能作为字典的键或放进集合。解决状态存入visited前转为元组或者在图的节点编号场景中直接使用整数编号。如果状态比较复杂可以考虑自定义序列化函数把局面压缩成字符串再哈希这也为后续做剪枝和缓存打基础。6. 收敛技巧双向 BFS 与 A* 的“BFS 换壳”双向 BFS 是把 BFS 从“能跑”改进到“快跑”的第一选择。原理很简单从起点和终点同时扩散每次选当前队列较短的的一侧扩展一层当两侧的 visited 集合相交时最短距离就是dist_from_start dist_from_end。在极端情况下比如图的平均分支因子为 10、最短路径长度为 20普通 BFS 需要展开 10^20 级别的节点双向 BFS 只需要两个方向的 10^10 级别差距是跨维度的。实际项目中处理八数码、单词接龙这种可控规模状态搜索双向 BFS 是性价比最高的优化几乎不需要调参。from collections import deque def bidirectional_bfs(nxt_func, start, target): # nxt_func: 输入状态, 返回邻居状态列表 # 两侧分别用 dist 字典记录距离 q_start, q_target deque([start]), deque([target]) dist_start, dist_target {start: 0}, {target: 0} while q_start and q_target: if len(q_start) len(q_target): cur_q, cur_dist, other_dist q_start, dist_start, dist_target flag start else: cur_q, cur_dist, other_dist q_target, dist_target, dist_start flag target for _ in range(len(cur_q)): cur cur_q.popleft() for nxt in nxt_func(cur): if nxt in other_dist: return dist_start.get(nxt, float(inf)) dist_target.get(nxt, float(inf)) if nxt not in cur_dist: cur_dist[nxt] cur_dist[cur] 1 cur_q.append(nxt) return -1逻辑说明每次扩展当前较短的队列能让两个搜索“尽量在中点相遇”。dist_get的双重判断是必要的如果相交节点在某侧已经是已访问节点直接从其距离字典取值即可。这个模板需要注意的一个点扩展一次不是只弹出一个节点而是弹一整层——上面代码里for _ in range(len(cur_q))就是干这个事的。如果只弹一个节点搜索会变成两个队列交叉单步虽然也能收敛但距离计算会出问题。A* 则可以理解为“把队列换成优先队列、把扩展顺序按启发值排序”的 BFS 变体。A* 保留了 BFS 的g值起点到当前点的真实代价额外加了h值当前点到终点的估算代价只要h满足可采纳性不大于真实剩余代价第一次扩展到目标时就是最短。实现时把deque换成最小堆visited换成记录best_g的哈希表即可。做地图寻路、游戏 AI 时A* 的优化效果比双向 BFS 更明显但要承担h函数设计的难度如果没有把握就先写 BFS 跑通再逐步替换。我个人的习惯是接到一个搜索需求先判断是否无权图无权图直接用 BFS 单向版本跑通数据规模不理想再换成双向 BFS有权图直接用 A* 或 Dijkstra不折腾 BFS 的变体。原因是写对 BFS 的成本最低把一个已知正确的 BFS 改成双向往返也很快直接上 A* 反而容易在启发函数上卡两天。这些年被 BFS 坑得最多的不是不会写而是“以为自己会写就跳过了边界判断和标记时机”。每次换项目、换语言重写 BFS 模板我都把visited标记时机、起点终点相等判断、边界检查三件事当作强制 checklist。希望这篇能从机制到源码帮你把 BFS 的每个参数都握在手里少走我走过的弯路。本文还有配套的精品资源点击获取