1. 从一张图说起DFS 和 BFS 到底在“搜索”什么我第一次意识到自己真正理解了 DFS 和 BFS不是在看算法课本的时候而是有天晚上帮朋友调一个“社交关系推荐”的小项目。需求很简单给我一个用户 ID找出他所有“朋友的朋友”里他还不认识的人。我第一反应就是遍历图但到底用深度优先还是广度优先我在草稿纸上画了十分钟才理清楚。这两个算法看起来简单实则每一步选择都藏在细节里。先做个最小化的定义DFS 是 Depth First Search深度优先搜索BFS 是 Breadth First Search广度优先搜索。它们解决的是同一个基础问题——在一个图结构里从一个起点出发按照某种规则访问所有能到达的节点。图是什么不用说得太抽象你只需要把它想成“一堆节点和连接它们的线”。社交网络里每个人是一个节点好友关系是线地图里每个路口是节点道路是线程序里每个状态是节点状态转移是线。搜索算法就是给你一个起点让你把这张网“走”一遍。但同样是走两种算法的性格完全不同。DFS 是“一条道走到黑”的执拗型选手选了一个邻居就一路深入直到走不动了才回头再换一条路继续。BFS 则是“层层推进”的稳健型选手先把离起点最近的一层全部访问完再进入下一层绝不跳级。这种性格差异决定了它们在不同问题中的命运。为了彻底看清它们的区别我构造一个非常小但足够说明问题的图A - B - C | | D - E - F邻接表表示如下按字母序排列邻居graph { A: [B, D], B: [A, C], C: [B, F], D: [A, E], E: [D, F], F: [C, E] }从 A 出发DFS 按照“先走字母序更小的邻居”这个规则访问顺序是A - B - C - F - E - D你看这个过程A 先到 BB 到 CC 到 FF 到 EE 到 D然后整条路走到头了才一层层回溯。整个过程像一根绳子从起点向外无限延伸先探最深的那一段。BFS 从 A 出发访问顺序是A - B - D - C - E - FA 先看自己直接相连的 B 和 D然后才轮到看“B 的朋友”和“D 的朋友”也就是 C 和 E最后才到 F。每一层都整整齐齐像波纹一样扩散。这一步如果只看伪代码可能觉得区别不大但真正落实到代码实现、复杂度分析、常见 bug 和场景选择差距就大了。下面我按两条线分别拆开讲每一段都会给出能直接跑起来的代码和踩坑记录。2. DFS 的三种写法递归、显式栈和迭代加深2.1 递归实现最直观但暗藏风险DFS 用递归写几乎是零思考成本。因为函数调用的系统调用栈天然就是“后进先出”的结构正好符合 DFS 的“沿一条路深入再回溯”语义。def dfs_recursive(graph, node, visitedNone): if visited is None: visited set() visited.add(node) print(node, end ) # 这里代表“访问”动作 for neighbor in graph[node]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited) return visited跑一下dfs_recursive(graph, A) # 输出: A B C F E D递归版本的可读性极好逻辑和“深度优先”的定义一一对应。但有一个工程上绕不开的问题递归深度。Python 默认递归深度大约在 1000 层左右如果图特别深——比如一条链表状的图有 5000 个节点——直接跑会抛出 RecursionError。这时候要么调大递归上限要么换显式栈。注意递归版本的 DFS对于深度很大的图不只是性能问题还有函数调用栈溢出的风险。写生产级代码前先评估图的最大深度。2.2 显式栈实现可控性更强但顺序有讲究显式栈的 DFS字面上就是用自己维护的栈替换系统调用栈。代码长了一点点但胜在稳不依赖递归深度。def dfs_iterative(graph, start): visited set([start]) stack [start] while stack: node stack.pop() print(node, end ) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor)有一个细节必须说清楚显式栈版本的访问顺序和递归版本可能不一样。以上面的图为例dfs_iterative(graph, A) # 输出: A D E F C B为什么因为递归版本是“边访问边递归”处理邻居 B 时会把 B 的整条链走完再回来而显式栈版本是先把所有未访问邻居压栈然后弹出的顺序取决于栈的 LIFO 行为。在这个写法里邻居 D 是最后压栈的但它最先被弹出所以 D 反而先被访问。这个差异本身不是错误关键看你关心的是什么。如果只关心“所有节点都被访问到”两种写法等价如果你需要特定的节点访问顺序必须理解清楚压栈与弹栈的先后关系。通常有一个推荐做法想让显式栈的访问顺序对齐递归版就“逆序压栈”——把邻居列表反转后再压进去def dfs_iterative_same_order(graph, start): visited set([start]) stack [start] while stack: node stack.pop() print(node, end ) # 逆序遍历邻居保证字母序小的先被处理 for neighbor in reversed(graph[node]): if neighbor not in visited: visited.add(neighbor) stack.append(neighbor)我实际写代码时如果没有特殊顺序要求我更倾向显式栈版本因为它不依赖递归深度调试时也更容易在循环里加日志。2.3 迭代加深 DFS深度优先但不无限深入还有一个容易被忽略的变体叫迭代加深搜索Iterative Deepening DFSIDDFS。它的思路很巧妙先限制 DFS 只能走 depth1看看能否找到目标找不到再把深限提高到 2、3…… 直到找到目标。这个东西看起来重复劳动很多但由于每层节点数量往往是指数增长多出来的开销其实可控而且它保留了 DFS 的低空间占用同时能保证找到最优解。它的适用场景搜索空间非常大但目标深度未知比如棋盘类游戏、状态空间搜索。不过对于初学者掌握递归版和显式栈版就够了迭代加深可以作为进阶了解。3. BFS 的分层机制为什么它天生适合最短路径3.1 用队列实现出队和入队的时机很关键BFS 的核心数据结构是队列先进先出。它的思想是把“当前层”的所有邻居全部入队然后依次处理再进入下一层。队列就像一条传送带保证先发现的节点先被处理。from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) while queue: node queue.popleft() print(node, end ) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)跑一下bfs(graph, A) # 输出: A B D C E F和 DFS 最大的不同在于BFS 的访问顺序天然就是“按距离分层”的。A 是第一层B 和 D 是第二层C 和 E 是第三层F 是第四层。这种“先近后远”的性质让 BFS 成为求解无权图最短路径的首选——因为第一次访问到目标节点时的层数一定是从起点到目标的最少边数。3.2 带步数的分层 BFS模板直接抄很多教材讲了 BFS 原理但真正到做题或写工程时会发现光知道“按层访问”还不够你得知道“当前在第几层”。一个非常实用的模板是在外层用for _ in range(len(queue))来区分层。def bfs_shortest_path(graph, start, target): visited set([start]) queue deque([start]) distance 0 while queue: for _ in range(len(queue)): node queue.popleft() if node target: return distance for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) distance 1 return -1这个for _ in range(len(queue))是很多人容易漏掉的细节。有了它distance才能和“层”对齐没有它distance累加的次数就完全错乱了。这个方法在网格类最短路径问题中特别有用比如二维矩阵迷宫寻路def shortest_path_in_grid(grid, start, end): grid: 0 可走, 1 障碍; start/end 为 (row, col) from collections import deque rows, cols len(grid), len(grid[0]) visited set([start]) queue deque([(start[0], start[1], 0)]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] while queue: r, c, dist queue.popleft() if (r, c) end: return dist for dr, dc in dirs: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] ! 1 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, dist 1)) return -1这里我直接在队列里存了步数省去分层循环。两种写法本质相同选哪种看你习惯。但要注意无论哪种写法visited 的标记必须在入队时完成这个问题我在后面的“常见坑”里集中说。3.3 双向 BFS从两端同时出发搜索量指数级下降如果搜索空间特别大单纯单向 BFS 可能很慢。一个实用优化是双向 BFS从起点和目标同时扩散每次扩展节点数更少的那一端直到两端相遇。对于无权图双向 BFS 能显著减少访问节点数因为它把“半径 r 的球体”变成“两个半径 r/2 的球体”在指数增长的空间里收益非常明显。伪代码如下def bi_bfs(graph, start, target): if start target: return 0 front, back {start}, {target} visited_front, visited_back {start}, {target} depth 0 while front and back: depth 1 # 优化从较小的集合扩展 if len(front) len(back): front, back back, front visited_front, visited_back visited_back, visited_front new_front set() for node in front: for neighbor in graph[node]: if neighbor in visited_back: return depth if neighbor not in visited_front: visited_front.add(neighbor) new_front.add(neighbor) front new_front return -1这个模板我建议存下来。LeetCode 上的很多“单词接龙”类问题用双向 BFS 比单向快出一个量级。不过注意双向 BFS 的前提是你知道明确的目标节点如果目标是“找所有可达节点”这种开放性问题就无从双向了。4. 选 DFS 还是 BFS一张对照表看清应用边界4.1 时空复杂度没想象中那么“一样”很多人背过结论DFS 和 BFS 时间都是 O(VE)V 是顶点数E 是边数。这个说法的前提是“每条边最多被检查一次”。但如果为了找某个目标就提前终止实际性能会因图结构差别巨大。空间复杂度才是真正的分水岭算法最坏空间复杂度说明DFS递归O(h)h 是递归深度极端情况是链表图hO(V)DFS显式栈O(h)栈中最多同时存储一条路径上的节点BFSO(w)w 是最大层宽度理想情况是根节点层宽极端情况是 O(V)举个例子一棵深度为 1000、每层只有 2 个节点的二叉树。DFS 的栈深度大约是 1000空间占用很稳定BFS 在某一层可能同时有 2^10 个节点但如果树是“宽而浅”的BFS 反而省空间。没有绝对的优劣只有图结构和目标问题的匹配度。4.2 场景对照什么时候无脑选 BFS我把常见问题分成两类直接看表问题类型推荐算法原因无权图最短路径、最少步数BFS第一次到达目标即最优找所有可达节点/连通分量DFS 或 BFS 均可只要求覆盖不要求顺序判断图中是否有环DFS递归回溯时天然能发现“回边”拓扑排序DFS 或 BFS 均可DFS 后序反转BFS 做 Kahn 算法全排列、组合、子集DFS回溯需要枚举所有状态路径迷宫是否有解只要结果DFS更早深入探索空间省迷宫最短路径BFS层数即步数树/图的层次遍历BFS天然按层输出搜索大量可行解中的第一个DFS尝试路径可能更快命中一个常见的面试题变体是“岛屿数量”给定二维网格1 代表陆地0 代表水求有多少块连通的陆地。DFS 和 BFS 都能做而且代码骨架几乎一样。区别在于 DFS 写起来更像“递归蔓延”BFS 则是“队列扩散”。这题考的不是算法难度而是你能不能选对遍历框架并在 visited 标记上不犯错。4.3 实践中的直觉怎么“秒选”算法我给自己的判断逻辑是这样一套短链这题的目标是“是否存在一条路径”还是“最短路径”后者直接选 BFS。是否需要回溯枚举所有可能性比如全排列、八皇后这类选 DFS。图的规模是“深”还是“宽”递归深度容易爆就选 BFS 或者显式栈 DFS。是否要按层输出结果比如按层级遍历二叉树选 BFS。是否需要在递归过程中记录一条完整路径DFS 天然维护路径栈更好操作。这套逻辑在大部分算法题里都能快速落地。真实工程里比如地图导航的最短路线你会选 BFS 或其进阶版 A*但如果是爬虫抓取整个网站链接结构你可能更需要 DFS 来控制爬取深度。没有“万金油”只有“合不合适”。5. 手写搜索最容易踩的坑visited 时机、递归深度与调试方法5.1 为什么必须在“入队/入栈时”标记 visited这是新手最容易踩的坑没有之一。BFS 代码如果写成“出队时标记 visited”会让很多节点被重复入队严重时甚至死循环。看下面这段有问题的 BFSdef bfs_wrong(graph, start): visited set() queue deque([start]) while queue: node queue.popleft() if node in visited: # 出队时才检查 continue visited.add(node) for neighbor in graph[node]: if neighbor not in visited: # 这里检查无效因为邻居可能已在队列里但未被处理 queue.append(neighbor)问题在哪假设图是A - B - C形成的三角形从 A 出发。A 先出队B、C 入队此时队列是 [B, C]。B 出队后它看到邻居 A已访问和 CC 已经在队列里但不在 visited 中于是把 C 又入队一次。队列变成 [C, C]。C 第一次出队时访问完C 第二次出队时发现 C 已在 visited 就跳过了。单独看这个例子勉强能跑只是多了一次无用入队。但如果图里有环结构这种“出队才标记”的写法会让队列指数膨胀甚至永远处理不完。正确做法很明确在把节点放入队列/栈的那一刻就标记为已访问。这一步不仅是为了避免重复也是保证算法在环状图上能终止的关键。5.2 递归深度导致崩溃一行代码解决但别依赖Python 里默认递归深度大约是 1000。如果你用递归 DFS 处理一个 2000 层深的图会直接抛 RecursionError。最简单的解法是加一行import sys sys.setrecursionlimit(1000000)这会调高限制。但我必须泼一盆冷水调高限制不等于没有代价。Python 的递归调用本身有函数调用开销而且太深的递归会让 C 栈面临真实风险在某些环境会直接段错误。我的建议是算法题里可以调为了过测试没问题生产代码里凡是你预计深度可能超过几百的直接用显式栈版本别赌系统栈空间。5.3 调试技巧把访问顺序打出来一切一目了然每次写完 DFS 或 BFS先别急着跑大数据用一个小图把访问顺序打印出来对比自己手推的顺序。这能帮你快速定位三类问题顺序不符合预期检查邻居遍历顺序、压栈是否逆序。节点被重复访问检查 visited 标记时机是否在入队/入栈前。该访问的节点漏掉了检查边界条件尤其是网格类问题的行列越界判断。网格问题还有一个特殊调试点方向数组别写错。dirs [(1,0), (-1,0), (0,1), (0,-1)]对应上下左右写成一个(0,0)就会原地踏步。我见过有人把(0, -1)写成(0, 1)导致整个搜索方向歪掉排查了半天才发现是方向定义问题。6. 从算法题到真实工程DFS/BFS 的实际用武之地6.1 算法题里的高频场景直接套模板刷 LeetCode 的朋友可以重点关注下面几类题它们都是 DFS/BFS 的“标准形态”二叉树遍历前序/中序/后序对 DFS层序对 BFS。网格类问题岛屿数量、腐烂的橘子、01 矩阵本质都是图搜索DFS/BFS 二选一。图论基础判断二分图、课程表拓扑排序、找桥找环。状态空间搜索单词接龙、最少转机次数这些基本都是 BFS 的天下。我特别想提一下“腐烂的橘子”这类多源 BFS 题。它的思路是把所有初始腐烂的橘子同时作为起点一起放入队列然后统一扩散。这其实就是把“单源 BFS”扩展成“多源 BFS”代码几乎一样只是初始队列里放多个节点。这种题对理解“层”和“步数”非常有帮助。6.2 工程实践爬虫、社交推荐、地图导航跳出刷题DFS/BFS 在真实项目里到处都是。我举几个自己经历过或见过的场景爬虫设计。爬取一个网站的所有子页面时BFS 是默认选择先抓首页的链接再抓这些链接指向的页面里的链接一层一层来。这样能避免爬虫陷入某个深不见底的目录结构里出不来。但如果目标是“精准抓取某一类深层页面”DFS 反而更合适因为它会优先沿着一条路径深入。社交平台的“你可能认识的人”。我的那位朋友做的功能核心就是一个 BFS从当前用户出发把“朋友”作为第 1 层“朋友的朋友”作为第 2 层排除自己已经认识的人把第 2 层按共同好友数排序返回。这就是典型的 BFS 分层排序。地图导航。虽然真实导航不会用纯 BFS但 BFS 是所有启发式搜索的地基。像 A* 算法本质上就是“带有启发函数的 BFS”它依然用队列的思想只是在选择下一个扩展节点时会优先选“距离目标更近”的方向。理解好基础 BFS再看 A* 会轻松很多。6.3 更进一步记忆化搜索和回溯法如果你已经熟练掌握了 DFS 和 BFS下一步我建议接触三个进阶方向回溯法DFS 的一种应用在全排列、组合、N 皇后问题中DFS 枚举所有路径并在不合条件时“剪枝”返回。记忆化搜索把 DFS 递归过程中计算出的子问题结果存起来避免重复计算本质是“DFS 缓存”。A* 搜索BFS 的启发式升级在工程中用于路径规划。这三个方向都以基础 DFS/BFS 为骨架只是针对不同问题加了策略。把今天这篇里的模板写熟练再往这几个方向走会顺畅很多。最后分享一个我自己的实操习惯不管多简单的搜图题我都坚持先画图、再写邻接表、然后手推一遍访问顺序最后才写代码。这个流程看起来是“多此一举”但它能帮你把抽象的算法变成具体的直觉。等你刷多了就会发现DFS 和 BFS 不是两种孤立的知识点而是你分析一切图结构问题的底层语言。