上一篇文章把BFS的基础板子讲完了，从队列实现到层序遍历，再到拓扑排序这类变体，相信动手敲过代码的朋友，对“广度优先”这四个字已经有了肌肉记忆。这篇是下篇，我不打算再把伪代码从头抄一遍，而是把重点放在你真正会遇到的三个问题上：怎么优化BFS让它不爆内存、什么时候该用DFS而不是BFS、以及BFS和A*算法的边界到底在哪里。顺便会聊几个真实项目里的落地场景，最后整理一份排查问题清单，都是我实际调试时踩过的坑，拿出来直接能用。
1. BFS算法进阶：从基础板子到实战变种
1.1 三种最常见的BFS优化方向
很多初学者以为BFS就是把起点丢进队列，然后while循环往外弹，四个方向挨个扩展。这个认知本身没错，但仅限于数据规模小的场景。一旦状态空间变大——比如在一个500×500的网格里找最短路径，或者在一个状态数百万的隐式图里搜索——裸BFS很容易卡在内存和时间两个瓶颈上。
我总结下来，实战中BFS最常见、收益最高的三个优化方向是这样的：
第一，双向BFS。如果起点和终点都是已知的，完全没必要从一头傻乎乎地扩展到终点，而是从起点和终点同时扩展，两边各自走一层，直到两个方向的搜索“撞上”。这种方式能把搜索深度直接砍半，状态数量呈指数级下降，在迷宫问题、单词接龙、字符串变换这类场景里表现非常明显。我实测过一个中等规模的迷宫，单向BFS要遍历两万多个格子，双向BFS只需要处理不到三千个，差距大概七倍。
第二，状态压缩。当每个状态不是简单的坐标(x, y)，而是由多个状态位组合而成时，比如一个3×3棋盘上每个位置有3种可能值，直接存整个盘面作为状态会导致内存爆炸。很多场景下可以把状态编码成一个整数——用位运算把几个变量的组合压到int甚至long里，判重数组直接用bool数组或bitset。这个技巧在八数码、华容道这类问题里几乎是必须的，不加压存根本跑不动。
第三，启发式剪枝（或者说贪心扩展顺序）。严格来说这已经不算纯BFS了，但很多人实际做BFS时会在扩展邻居前先对邻居排个序，优先扩展“看起来更接近目标”的方向。这种做法在数据有明确几何意义时效果很好，比如网格寻路中优先走靠近终点的方向，虽然不能保证一定减少最坏情况，但在平均情况下能显著减少探索量。要注意的是，这种方式失去了BFS第一个找到的解就是最优解的特性，如果题目要求严格最优，必须配合A*那种带估价函数的思路来保证。
1.2 双向BFS的原理与代码模板
双向BFS的核心逻辑如果用一句话概括，就是“两个队列交替扩展，每一轮选小的那边走”。选边小的那个扩展是为了控制内存和计算量，因为每扩展一层，状态数大致是上一次的分支因子的乘方，从小的那头扩展，能让总探索量保持在相对低的水平。
我以经典的“单词接龙”问题为例，题目是给出beginWord、endWord和一个词典，每次只能改一个字母，问从begin到end的最短转换序列长度。这个题用双向BFS非常典型，直接上模板：
from collections import deque def ladderLength(beginWord, endWord, wordList): if endWord not in wordList: return 0 # 做一层set转换，方便快速判断是否存在 wordSet = set(wordList) # 两个方向的队列，还附带当前已走的步数 q_begin = deque([(beginWord, 1)]) q_end = deque([(endWord, 1)]) # 两个方向的访问标记 visited_begin = {beginWord: 1} visited_end = {endWord: 1} while q_begin and q_end: ans = -1 if len(q_begin) <= len(q_end): ans = extend(q_begin, visited_begin, visited_end, wordSet) else: ans = extend(q_end, visited_end, visited_begin, wordSet) if ans != -1: return ans return 0 def extend(q, visited_cur, visited_other, wordSet): # 每次只扩展当前队列的一整层 for _ in range(len(q)): word, step = q.popleft() for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': if c == word[i]: continue new_word = word[:i] + c + word[i+1:] if new_word in wordSet: if new_word in visited_other: return step + visited_other[new_word] if new_word not in visited_cur: visited_cur[new_word] = step + 1 q.append((new_word, step + 1)) return -1两个队列交替扩展，谁短就扩谁，每一次扩展一整层的节点，然后检测当前层产生的新节点有没有出现在对方的访问集合里，一旦出现，两边步数加起来就是最短路径长度。这段代码我在多个类似题上直接套过，性能比单向BFS好很多。
这里有个关键点要注意：双向BFS只适用于“终点已知”且“路径可逆”的搜索。如果终点状态不确定，或者扩展方向有严格单向性（比如只能从入度小的走向入度大的），双向BFS就失效了。
1.3 状态压缩BFS：当队列里放的不再是简单坐标
有些问题表面上看是BFS，但状态不是坐标，而是一个“状态的组合”。我拿经典的“打开转盘锁”来举例，四个轮盘每个盘0到9，每次可以拨动一个盘一步，给出一组死亡数字，避免出现，求从“0000”到目标数字的最短步数。
这个题如果直接用字符串作为状态，每个状态按字符串比较判重，时间会慢到难以接受。实际工程里我倾向于把四位数字编码成一个整数，每一位占3个bit，用一个int来表示状态，然后用bool数组做10^4大小的判重标记。这样判重是O(1)的，状态处理也快。类似地，八数码问题可以压缩成一个long，用康托展开或者全排列哈希来做判重。
压缩状态这种技巧，本质上是在“可接受的编码复杂度”和“运行性能”之间做置换。写起来确实比直接用结构体或者字符串麻烦一些，但一旦状态空间超过几百万，这种置换就是决定性的。不少竞赛题和面试题卡的就是这一点。
2. BFS与DFS终极对决：该怎么选
2.1 两者最本质的差异
BFS和DFS的选择问题，几乎是所有学完这两个算法的人都会纠结的问题。我在带新人的时候最喜欢打一个比方：BFS是地毯式排查，DFS是一条道走到黑，撞了南墙再回头。
BFS一层一层往外扫，先发现的目标路径一定是最短路径（在无权图中），这是它最大的优势。但代价是它需要把当前层的所有节点都记下来，空间复杂度通常和状态空间的宽度成正比。DFS正好反过来，它只需要维护当前路径上的节点栈，空间上很省，但不撞到头不知道目标在哪，所以找到的第一个解不保证最优。
还有一个很多人忽略的点：DFS天然适配递归写法，BFS天然适配迭代写法。有些问题——比如判断图的连通分量数量、拓扑排序、找环——DFS写起来极其顺手，三五行搞定。但你要是递归深度超过Python默认的1000层，就会碰到RecursionError，这时候又得改写成显式栈的迭代版，麻烦得很。BFS则没这个问题，队列迭代天然稳定。
2.2 通过四道经典题看选型策略
我知道光讲理论没有参考价值，直接上几个经典问题，看看在真实场景里到底该怎么选。
**问题一：求二叉树的层序遍历。**这个是BFS的招牌题目，几乎没有任何讨论的余地，直接用层序模板。你要用DFS也能写层序遍历，但需要额外记录每个节点所在深度，再按深度归组，代码复杂度明显上升，而且最容易写错的地方是不知道什么时候该新建一层列表。BFS天然按层走，每次while循环处理一整层，结构上一清二楚。
**问题二：判断一棵二叉树是否对称。**这个题看起来像是树的递归题，但你用BFS也能做。用队列迭代比较左子树和右子树对应的节点，本质上是一种双端扩展的BFS变形。我个人的习惯是：凡是需要把问题拆成子问题递归求解的，优先DFS；凡是需要按层比较或按层输出的，优先BFS。
**问题三：在迷宫中找到一条可行路径（不要求最短）。**这个用DFS其实更顺手，因为只需找到一个解就能返回，DFS能快速扎进深处碰运气，BFS则会先把起点附近所有格子都铺满，浪费不少时间。不过由于面试题大多要求“最短路径”，所以BFS反而成了标准答案。如果是工程上只求连通性，DFS更省内存。
**问题四：判断有向图是否有环。**DFS配合三色标记法是经典解法，写起来最自然，因为递归返回的时候天然能处理“回溯”。也可以用BFS做，思路就是拓扑排序——不断把入度为0的节点剔除，如果最后还有节点剩下，说明有环。两种都能解，但从易读性和写代码的效率来说，DFS三色标记法更直接。
2.3 我在实际开发中的选型经验
说了这么多，给你一个我自己用了很多年的判断标准，遇到搜索问题先按这个思路过一遍：
- 先看题目是否要求“最短路径”或“最少步数”——如果是，直接上BFS（无权图）或Dijkstra/A*（有权图）。
- 如果不要求最短，只看是否存在某条可达路径——用DFS更省内存。
- 如果状态空间无限大（比如某些状态生成规则不确定），DFS容易陷入死循环，必须用BFS限界。
- 如果递归深度可能超过语言限制，果断用BFS或者显式栈的DFS。
说白了，选BFS还是DFS，不是看哪个算法“更高级”，而是看搜索目标、状态空间、路径要求这三件事的综合约束。
3. BFS与A*算法：从盲目搜索到启发式搜索
3.1 A*算法到底改了什么
A算法在BFS的基础上引入了一个估价函数f(n) = g(n) + h(n)，其中g(n)是从起点到当前节点n的实际代价，h(n)是从当前节点n到终点的估计代价。BFS可以看作是h(n)恒等于0的特例，Dijkstra则是g(n)为实际边权、h(n)恒等于0的另一个特例。A的核心在于：它不再盲目地按“先入队先扩展”的顺序搜索，而是每次都优先扩展f(n)最小的节点。
这里最关键的细节是h(n)的选取。h(n)必须满足“可采纳性”，也就是h(n)永远不能高估到终点的实际代价，这样A*才能保证找到最优解。工程上用的最广的启发式函数是欧几里得距离和曼哈顿距离，在网格地图里曼哈顿距离用得最多，因为大部分移动模型是上下左右四方向，两点之间的实际最短距离恰好是曼哈顿距离的下界。
我在一个项目里做过一个路径规划模块，同样一张地图，用BFS的原始版本跑，扩展了大概12000个节点才找到目标；换上曼哈顿距离的A*，扩展节点数骤降到2500左右，差距接近80%。在地图规模变大后，这种差距会被进一步拉大，A*几乎成了网格寻路的事实标准。
3.2 一张表看明白BFS、Dijkstra、A*各管什么
很多人混淆BFS、Dijkstra和A*这兄弟三个，我用一张表把它们的区别摊开了说：
| 算法 | 边权要求 | 搜索方向 | 适用场景 | 最优性保证 |
|---|---|---|---|---|
| BFS | 所有边权相同（无权图） | 盲目，从起点均匀扩展 | 迷宫最短步数、分层遍历 | 有（基于层数的最短路径） |
| Dijkstra | 边权非负，可以不同 | 盲目，按累计代价扩展 | 最短路径（带权图） | 有（基于累计代价的最小路径） |
| A* | 边权非负，且需要启发函数 | 有向，启发式引导 | 大规模静态地图寻路 | 有（前提是h(n)可采纳） |
做题的时候，如果你确定图中每条边的代价都一样，直接BFS，因为它的实现最简，性能也够。如果边的代价不一样且目标单一，Dijkstra更通用。一旦地图很大且目标点固定，A*是首选。这三者的选择本质上是“用多少先验信息来加速搜索”的权衡。
3.3 我从BFS换到A*的三个信号
并不是说A*一定比BFS好，它有两个额外成本：需要设计可采纳的启发函数，需要维护优先队列。我用过一段时间后总结出三个换算法的信号：
第一，地图规模大到BFS的等待时间不可接受。我自己的经验数值是，节点数超过百万级时，纯BFS会在扩展上层节点时消耗大量内存和时间，A*的启发引导能有效避免“四面八方乱扩”。
第二，地图上的移动代价变得不均匀。比如在一个游戏地图里，有些地形是泥地，移动代价是平原的三倍。这时候BFS的“层”这个概念已经失真，Dijkstra和A*才是正确工具。
第三，需要反复做多次查询。如果同一张地图上要计算大量点到点的最短路径，A*配上预处理好的启发信息可以缓存一些中间结果，比每次从头BFS快很多。
反过来，如果题目只是一个小规模的网格找最少步数，用A*反而是过度设计——优先队列的log n开销和启发函数的计算成本可能比直接BFS还慢。
4. 实战复盘：BFS在真实项目里的三个应用场景
4.1 游戏寻路：为什么90%的时候BFS就够用
说到游戏寻路，很多人脑子里第一个冒出来的是A*。但实际上，在很多轻量级游戏或原型开发阶段，BFS完全够用，而且更容易实现和维护。我记得曾在做一个小型2D RPG项目的时候，怪物追主角的逻辑一开始就是简单的四方向BFS，地图大小大概是80×60的格子，地图几乎不会有变化，NPC数量不多，每帧跑一次BFS的耗时基本可以忽略。
BFS在这个场景里能用的前提有两个：一是地图规模小，二是移动代价均匀。如果这两个条件不满足，才会考虑A*。如果你想在工程里把地图做得大一点，建议的做法是先用BFS做一版让功能跑通，观察性能，瓶颈出现了再优化成A*。不要一上来就上重武器，过早优化是万恶之源这句话在寻路模块里特别适用。
4.2 网络爬虫与数据抓取：BFS的天然主场
网络爬虫其实就是一个典型的BFS过程。起始URL作为种子节点，把它指向的所有链接（出边）抓下来加入待抓取队列，然后一层一层往外爬。这也意味着，爬虫天然是由近及远地优先抓取浅层页面，而不像DFS那样沿着某条链一路爬到很深的地方再回来。这种策略不仅在实现上更直观，对目标网站的服务压力也更小，对整站抓取来说更友好。
我在一个数据采集项目里就是用BFS的思想管理URL队列的。核心流程是：维护一个待抓取URL的FIFO队列，每个URL解析出来的新链接先去重，然后入队，一级页面抓完自然到了二级页面，网络结构和层级关系清清楚楚。这里有个关键细节：去重必须做到位，也就是用visited集合记录已抓取的URL，否则一个互相链接的站群能让你无限死循环。BFS的这个“按层扩展”特性，还在很多需要按关系层级抓取的场景里成了默认选择。
4.3 社交网络中的六度分隔：BFS在关系图谱里的计算
六度分隔理论说，世界上任何两个人之间的社交距离不超过六层。在社交网络里计算两个人之间的最短关系路径，本质上就是在一个巨大的无向图（或关注关系有向图）里跑BFS。这个场景我实际写过，一个几十万节点的子图，单向BFS在层数较深时已经有点吃力，但用双向BFS从两个用户同时向外扩展，经常能在两三层内就相遇，速度快得惊人。
我做过的项目是给一个内部协作工具做“同事关系最短链”的功能。用户输入两个成员的名字，后端在组织关系图里跑双向BFS，返回一条最短路径，展示“你认识他，他认识她，她认识目标”这样的链条。数据规模不算大，但调用频率高，所以接口要求毫秒级响应。双向BFS在这种场景里几乎完美匹配需求。这也印证了我前面的观点：多学习双向BFS的思维，在真实工程里它的性价比极高。
5. 常见问题与排查技巧实录
5.1 内存爆炸：如何定位和解决BFS状态膨胀
BFS最常见的运行时问题就是内存占用过高，尤其是状态空间大的时候。我见过一个新手写的迷宫BFS，把每一步的完整坐标路径都存到了队列节点里。坐标路径是什么概念？从起点到当前位置的所有坐标列表。在一条长路径上，一个节点就存了几百个坐标，几千个节点全部入队的时候，内存直接翻车。
排查思路其实就是问自己三个问题：**每个队列节点里到底存了什么？访问标记数组是用什么实现的？有没有在入队前做判重？**这三个问题对应三个优化手段：
第一，节点只存必要信息。能存坐标索引就存索引，路径信息单独用数组记录，不要跟着队列走。
第二，判重数组尽量用一维或二维bool数组。Python里set虽然方便，但每个元素都要存哈希，内存开销比同规模的数组高很多。能用数组优先用数组，实在要动态扩展再用set。
第三，入队和标记必须同步。很多人习惯先push再标记，结果同一个节点被重复入队多次，队列长度暴增。正确做法是：在决定入队的那一刻就把visited标记好。
我之前测试过两个版本的迷宫BFS，一个用set存字符串坐标，一个用二维bool数组判断，同样地图下前者内存大约是后者的8倍，运行时间也多了一半。别小看这些细节，在面试或者比赛中，这就可能是超时和过关的分水岭。
5.2 死循环：什么情况下BFS会无限跑下去
BFS本身不会出现“递归层数过深”的栈溢出问题，但死循环的风险一点都不小。最常见的死循环原因是状态空间没有终止条件，或者不加visited判重直接跑。
举个例子，在不带判重的图里跑BFS，只要两个节点之间有双向边，算法就会在这两个节点之间来回震荡，永远出不来找不到终点。更隐蔽的情况是，图的生成规则里存在环，visited判重虽然能防止节点重复扩展，但如果你在用set判重时，每个状态都包含一个“当前路径长度”信息，那即使节点相同、路径长度不同，你也可能把它当成“新状态”反复入队，导致状态数量爆炸甚至死循环。
区分是不是死循环的排查方法也很简单：在扩展每个节点时计数，打印被扩展的节点总数。如果这个数字远远超过理论上限——比如一个一千个格子的迷宫跑出了一千万次扩展——那基本可以判断是判重逻辑有问题。
5.3 常见报错和解决方案速查表
我把BFS实战中常见的错误类型整理成一张速查表，方便你按图索骥：
| 症状 | 可能原因 | 解决方案 |
|---|---|---|
| 队列无限增长 | 入队前未判重；图有环且无访问标记 | 入队时同步标记visited |
| 运行超时 | 用的数据结构太低效（如list做队列pop(0)）；判重用set且状态过多 | 换collections.deque；判重数组化；考虑双向BFS |
| 内存溢出 | 队列节点存了过多冗余信息；状态未压缩 | 精简节点字段；状态压缩为整数 |
| 结果错误（偏大） | BFS没有按层扩展，混用了DFS逻辑 | 每次while循环处理一整层，不要逐节点处理 |
| 结果错误（偏小） | 终点判重过于提前，导致绕近路 | 在节点出队时再判断是否到达终点，而不是入队时判断 |
这些坑我在实际刷题和项目里都遇到过。比如“出队时判断还是入队时判断”这个问题，很多教程没有讲清楚。如果入队时就判断目标，那第一次把目标节点加入队列的那一层，可能还有同一个甚至更短的路也通向这个目标，但因为该节点已经被标记visited就错过了，结果就会偏大。正确的做法是：把终点判断放在出队时，确保当前出队的节点是全局f值最小的那一层，这时才能确认最短路径。
5.4 我常用的三个调试技巧
调试BFS和调试其他算法有点不同，因为状态空间大、层数多，靠print干瞪眼效率很低。我的习惯是：
第一个技巧：写一个小的可视化函数，把当前扩展过的节点打印成网格，每扩展一层打印一次。代码量不大，但对理解算法行为帮助极大。尤其当答案错误时，你看一眼扩展过的节点分布图，就知道是没按层扩展，还是方向判断错了。对于力扣这类算法题，直接在本地搭一个小的输出框架就行。
第二个技巧：刻意测试边界场景。比如只有起点的迷宫、起点就是终点、目标不可达、图中有多个最短路径。这些边界情况最容易暴露“出队判断”和“入队判断”这类细节问题。不用想着用大数据测试，小边界用例往往一击致命。
第三个技巧：用随机小图对比BFS和Floyd或者暴力搜索的结果。比如生成一个小的随机图，跑一遍BFS，再用O(n^3)的Floyd或者观察法手算验证。这种对拍思路在算法调试里非常有效，能自动找反例，比自己盯着错误输出猜要高效得多。
6. BFS的常见变体和扩展思路
到这里，BFS的基础、优化、选型、工程场景、调试技巧都讲完了。但我还想再聊聊BFS这个算法的“外延”。很多人在学完一篇BFS教程后，只能解决“迷宫最短路”这唯一一类问题，但实际上BFS的变体覆盖的范围比我上面写的还要广。
比如0-1 BFS，专门处理边权只有0和1的图，把普通队列换成双端队列，0权边从队头插入，1权边从队尾插入，这样仍然能保证按代价递增的顺序处理节点，时间复杂度是O(V+E)，比Dijkstra更加轻量。再比如多源BFS，把多个起点同时丢进队列，一开始就填充所有源的层数为0，这种做法在求“地图上每个格子到最近一个源点的距离”这类问题里非常好用。
还有一个思路值得提一下，那就是把BFS和二分答案结合起来。在某些约束优化问题里，我们会“二分答案，然后用BFS判断可行性”。这种组合在竞赛题里很常见。虽然严格来说不算BFS变体，但它展示了BFS作为“判定器”的灵活性。
这些扩展思路不用急着全掌握，但你得知道它们的存在。实际工作里碰到“感觉跟最短路有点像但又不太一样”的问题时，先别急着写Dijkstra，冷静下来想想能不能用0-1 BFS或者多源BFS把模型简化掉。
我个人做了几年算法相关的工程，最大的体会是：BFS的真正价值不在于那二十行模板代码，而在于“逐层推进”和“状态标记”这两个底层思维模型。碰到一个新问题，你如果能把状态定义清楚，把转移方式和判重方式想明白，BFS就成功了一半。剩下那部分，多写几道题自然就有了。
这次下篇的内容就到这里。如果你在实操中遇到BFS相关的问题，欢迎带着代码来讨论，我看到了会尽量回复。
