1. 项目概述从“搜索”到“路径”的思维跃迁“搜索”这个词在计算机科学里远不止是你在浏览器里敲几个关键词那么简单。它更像是一个探险家在未知地图上系统性地探索每一个角落直到找到宝藏的过程。而DFS深度优先搜索和BFS广度优先搜索就是这位探险家最基础、也最核心的两种“探险策略”。无论你是刚入门数据结构与算法的新手还是已经工作多年、需要快速回顾核心思想的开发者理解这两种搜索策略就如同掌握了打开“图论”和“状态空间”这两座宝库的万能钥匙。它们不仅是解决“迷宫问题”、“棋盘问题”的理论基础更是构建更复杂算法如A*、Dijkstra的基石。今天我们就抛开枯燥的教科书定义从“为什么需要这两种策略”以及“它们到底解决了什么问题”入手用最贴近实战的视角把DFS和BFS掰开揉碎了讲清楚。2. 核心思想与场景对比深度与广度的哲学在深入代码之前我们必须先理解这两种策略背后的根本逻辑。这决定了你在遇到实际问题时能否第一时间做出正确的选择。2.1 深度优先搜索一条路走到黑DFS的核心思想用一个词概括就是“递归”或“栈”。想象一下你在探索一个巨大的地下洞穴。DFS的策略是选择一条岔路就一直往里走走到尽头碰壁后再退回上一个岔路口选择另一条没走过的路继续深入。它的行为模式是纵向的、深入的。这种策略非常适合解决那些需要遍历所有可能状态或者寻找一条可行路径而非最短路径的问题。比如走迷宫时只要你不在乎走了多少弯路只关心能不能走出去用DFS就非常合适。再比如在排列组合问题中如全排列、子集生成你需要枚举所有可能的情况DFS通过递归可以非常优雅地实现这种“尝试-回溯”的过程。注意DFS在探索过程中如果图或树中存在环路且没有记录已访问状态就会陷入无限循环。因此维护一个visited集合来标记已访问节点是DFS实现中的关键一步。2.2 广度优先搜索层层递进的探索BFS的核心思想则是“队列”。还是那个地下洞穴BFS的策略是你站在起点先把你目光所及一步能到达的所有岔路口都探索一遍记录下这些位置。然后你再从这些新发现的洞口出发探索从它们出发、一步能到达的所有新洞口。如此一层一层地向外扩散。它的行为模式是横向的、层级的。这种策略天然适合求解“最短路径”或“最少步骤”问题。因为BFS保证当它第一次访问到目标节点时所经过的层数即步数一定是最少的。典型的应用场景包括社交网络中查找两个人之间的最短关系链几度分隔、棋盘上骑士走到某个位置的最少步数、单词接龙的最短转换序列等。2.3 决策矩阵我该用DFS还是BFS光知道定义不够关键是要会在实际中选。下面这个表格总结了核心的决策逻辑特性维度深度优先搜索广度优先搜索数据结构栈 (递归调用栈或显式栈)队列遍历顺序深度优先纵向深入广度优先层层推进空间复杂度O(h)h为递归深度/图的最大深度。在树中表现好。O(w)w为图中最宽层的节点数。在稠密图中可能很高。经典适用场景1. 拓扑排序2. 检测图中环3. 寻找连通分量4. 解决所有解问题如八皇后5. 路径存在性判断不要求最短1.无权图的最短路径2. 层次遍历如二叉树层序遍历3. 扩散类问题如腐烂的橘子、岛屿数量4. 状态空间搜索求最优解一个关键比喻探险家认准一条路走到黑不行再回头。广播信号波纹一样从中心一圈圈扩散出去。实操心得很多初学者容易混淆。一个简单的记忆方法是问自己“我要找的是所有可能还是最优最短的那个”。如果是“所有可能”或“是否存在”优先考虑DFS如果是“最短/最少”几乎可以确定用BFS。当然有些问题两者都能解但效率和侧重点不同。3. 算法实现细节与代码模板理解了思想我们来看如何用代码实现。这里我会给出清晰、可复用的模板并解释每一行代码的意图。3.1 深度优先搜索的两种实现方式DFS有两种常见的实现方式递归和显式栈。递归写法简洁体现了DFS“回溯”的本质显式栈则避免了递归深度过大导致的栈溢出问题。递归版DFS模板以图的遍历为例def dfs_recursive(node, visited, graph): :param node: 当前访问的节点 :param visited: 集合记录已访问节点 :param graph: 邻接表表示的图graph[node] 是 node 的邻居列表 # 1. 处理当前节点例如打印、记录路径等 print(node) # 2. 标记当前节点为已访问 visited.add(node) # 3. 遍历当前节点的所有邻居 for neighbor in graph[node]: # 4. 如果邻居未被访问则递归访问 if neighbor not in visited: dfs_recursive(neighbor, visited, graph) # 函数结束自动回溯到上一层调用者显式栈版DFS模板def dfs_iterative(start, graph): visited set() stack [start] # 使用列表模拟栈后进先出 while stack: node stack.pop() # 弹出栈顶元素 if node not in visited: # 处理当前节点 print(node) visited.add(node) # 将邻居压入栈中。注意为了与递归顺序一致假设邻接表是正序 # 可能需要将邻居逆序入栈以保证第一个邻居最后入栈、最先弹出。 for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor)关键点解析递归版的visited.add(node)发生在处理节点之后、遍历邻居之前这能防止重复处理。显式栈版中我们在pop出节点后才检查是否访问这是因为同一个节点可能被多次加入栈中通过不同的父节点我们只在真正处理它时才标记访问避免漏掉某些路径在某些特定问题中。这是DFS实现中一个非常容易出错的细节。3.2 广度优先搜索的队列实现BFS的实现通常使用队列模式非常固定。BFS模板以图的遍历为例from collections import deque def bfs(start, graph): visited set([start]) # 标记起始点已访问 queue deque([start]) # 双端队列高效实现FIFO while queue: # 1. 弹出队列头部节点 node queue.popleft() # 2. 处理当前节点例如如果是找最短路径这里可以判断是否到达目标 print(node) # 3. 遍历当前节点的所有邻居 for neighbor in graph[node]: if neighbor not in visited: # 4. 标记邻居为已访问并加入队列尾部 visited.add(neighbor) queue.append(neighbor)与DFS的关键区别BFS在将邻居加入队列之前就标记为visited。这是因为在BFS中节点一旦被加入队列它迟早会在某一层被处理。如果在popleft时才标记可能导致同一个节点被多个上层节点重复加入队列造成冗余计算甚至在存在环的图中导致无限循环。这个“早标记”是BFS模板的一个铁律。3.3 路径记录如何知道我们是怎么走过来的单纯的遍历节点往往不够我们通常需要记录从起点到目标节点的完整路径。这需要在搜索过程中维护每个节点的“父节点”信息。BFS记录路径的改进模板from collections import deque def bfs_path(start, target, graph): if start target: return [start] queue deque([start]) # parent字典记录每个节点的前驱节点用于回溯路径 parent {start: None} visited set([start]) 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 [] while neighbor is not None: path.append(neighbor) neighbor parent[neighbor] # 向上回溯 return path[::-1] # 反转路径从起点到终点 return None # 未找到路径DFS记录路径在递归DFS中路径隐含在调用栈里。我们可以在递归函数中传递一个path列表在进入节点时加入离开节点时弹出回溯当找到目标时当前的path就是一条可行路径。注意DFS找到的第一条路径不一定是最短的。4. 经典问题实战走迷宫与单词接龙理论结合实战才能融会贯通。我们通过两个LeetCode经典问题来看DFS和BFS如何具体应用。4.1 实战一DFS解迷宫所有路径LeetCode 980. 不同路径 III这个问题是DFS回溯的经典应用在网格中从起点走到终点必须经过每一个空格一次求所有不同路径数。这完美契合了DFS需要探索所有可能状态的特点。解题思路首先遍历网格找到起点(sr, sc)并统计必须经过的空格总数steps_to_do包括终点不包括起点。从起点开始DFS。每次向四个方向移动。维护一个visited集合或直接修改网格为-1来标记已访问防止重复访问。当到达终点时检查已走过的步数是否等于steps_to_do。如果是则找到一条有效路径。回溯在从当前节点返回上层递归前需要撤销访问标记以便其他路径可以再次经过此点。核心代码框架class Solution: def uniquePathsIII(self, grid): rows, cols len(grid), len(grid[0]) start end None steps_to_do 1 # 初始化1会把终点也算进去 # 1. 找到起点、终点并统计必须走的步数 for r in range(rows): for c in range(cols): if grid[r][c] 1: start (r, c) elif grid[r][c] 2: end (r, c) elif grid[r][c] 0: steps_to_do 1 self.answer 0 directions [(0,1), (0,-1), (1,0), (-1,0)] def dfs(r, c, steps_walked): # 2. 终止条件到达终点 if (r, c) end: if steps_walked steps_to_do: self.answer 1 return # 3. 标记当前单元格为已访问用-1表示 temp grid[r][c] grid[r][c] -1 # 4. 遍历四个方向 for dr, dc in directions: nr, nc r dr, c dc # 确保新位置在网格内且是可行走的0或2 if 0 nr rows and 0 nc cols and grid[nr][nc] in (0, 2): dfs(nr, nc, steps_walked 1) # 5. 回溯撤销访问标记 grid[r][c] temp dfs(start[0], start[1], 0) return self.answer避坑技巧在网格DFS中修改原数组进行访问标记是一种节省空间的常用技巧。但务必记得在回溯时恢复原状否则会影响其他分支的搜索。另外将方向数组directions定义为类变量或局部常量比在递归函数内重复创建更高效。4.2 实战二BFS解单词接龙最短路径LeetCode 127. 单词接龙给定一个起始词、一个结束词和一个单词列表每次只能改变一个字母找出从起始词到结束词的最短转换序列长度。这明显是一个“最短路径”问题每个单词是一个节点相差一个字母的单词之间有边用BFS再合适不过。解题思路将单词列表转换为集合word_set便于O(1)时间查询。使用队列进行BFS。队列中的元素可以是(current_word, current_length)。对于队列中的每个单词生成它所有可能的下一个单词即改变每一个位置的字母为a-z检查是否在word_set中或是结束词。为了加速和防止环路一旦一个单词被访问过就将其从word_set中移除这同时起到了visited集合的作用。当弹出的单词等于结束词时返回当前的转换长度。优化点直接生成所有可能的下一跳单词其复杂度是 O(26 * L)其中L是单词长度。这比遍历整个单词列表O(N)来比较每个单词要快得多尤其是在单词列表很大时。核心代码实现from collections import deque class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) - int: word_set set(wordList) if endWord not in word_set: return 0 queue deque([(beginWord, 1)]) # (当前单词 当前路径长度) word_set.discard(beginWord) # 移除起始词避免重复使用 while queue: current_word, current_length queue.popleft() # 如果找到终点返回长度 if current_word endWord: return current_length # 尝试改变当前单词的每一个位置 for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue # 跳过与原字母相同的改变 next_word current_word[:i] c current_word[i1:] # 如果新单词在集合中说明是有效转换 if next_word in word_set: word_set.remove(next_word) # 关键移除相当于标记已访问 queue.append((next_word, current_length 1)) return 0实操心得在BFS中visited标记的时机至关重要。这里采用了一旦发现新单词就立刻从word_set中移除的策略这保证了每个单词只会被入队一次既防止了环也保证了第一次找到结束词时的路径就是最短的。这是一种非常高效且常见的“就地”访问标记法。5. 性能分析与优化策略理解了基础实现我们还需要知道它们的局限以及如何优化。5.1 时间复杂度与空间复杂度DFS时间复杂度一般为 O(V E)其中V是顶点数E是边数因为每个节点和边最多访问一次。空间复杂度主要取决于递归深度最坏为 O(V)当图退化成一条链时。BFS时间复杂度同样为 O(V E)。空间复杂度则取决于队列中最多同时存放多少节点在最坏情况下如完全二叉树最后一层可能达到 O(V)。一个常见的误解认为DFS一定比BFS省空间。这不一定。在平衡树中BFS的空间复杂度 O(N) 可能大于DFS的 O(logN)但在一个深度很大但宽度很小的图如一条长链中DFS的递归栈空间 O(V) 可能远大于BFS的队列空间 O(1)。需要具体问题具体分析。5.2 栈溢出与迭代深化搜索递归DFS最大的风险是栈溢出。当递归深度过深例如上万层就会触发递归深度限制错误。解决方法有两个改用显式栈的迭代实现如前文所述用自己维护的列表模拟栈通常比系统调用栈能承受的更深。迭代深化搜索这是一种结合了DFS空间优势和BFS最优性优势的算法。它限定一个深度depth在这个深度内进行深度优先搜索。如果没找到目标就将深度限制depth加1重新开始搜索。虽然会重复搜索浅层节点但它的空间复杂度是 O(d)d是目标深度并且能找到最短路径如果路径代价是深度。在状态空间很大、深度未知且要求最优解时IDS是一个不错的选择。5.3 双向BFS大幅缩减搜索空间对于已知起点和终点的最短路径问题双向BFS是性能优化的利器。它从起点和终点同时开始进行BFS。当两个方向的搜索相遇时路径就找到了。为什么更快假设分支因子是b最短路径长度是d。传统BFS需要探索的节点数量级是 O(b^d)。而双向BFS从两头出发理想情况下在中间点相遇每边只需要探索深度约为 d/2 的节点总探索量级约为 O(b^{d/2} b^{d/2}) O(2 * b^{d/2})这比 O(b^d) 指数级地减少了。实现要点使用两个队列或集合分别代表从起点和终点开始的搜索前沿。使用两个字典分别记录从起点和终点到各个节点的距离或路径。每一轮选择节点数较少的那一边进行扩展以平衡两边的搜索进度。当某个节点同时出现在两个已访问集合中时说明相遇路径长度为两边距离之和加1。在单词接龙问题中使用双向BFS可以将性能提升一个数量级。6. 从基础搜索到高级算法DFS和BFS不仅是独立的算法更是构建更复杂算法的组件。理解它们是通向高级图论和搜索算法的必经之路。6.1 拓扑排序DFS的后序遍历拓扑排序用于解决有向无环图的节点线性排序问题使得对于任何有向边 (u, v)u 在排序中都出现在 v 之前。DFS是实现拓扑排序的经典方法对图进行DFS在某个节点的所有邻居都被访问完成后将该节点“后序”加入结果列表最后将结果列表反转即可得到拓扑排序。Kahn算法基于入度则是BFS思想的体现。6.2 连通分量与并查集查找无向图中的连通分量DFS/BFS是最直观的方法从一个未访问的节点开始进行一次完整的DFS或BFS所有能访问到的节点就构成一个连通分量。而并查集则是解决此类问题的另一种高效数据结构它能在近乎常数时间内合并两个集合和查询两个元素是否属于同一集合在某些场景下比搜索更高效。6.3 A*搜索算法启发式引导的BFS当图中的边带有不同的代价或权重时BFS就不再保证找到的是最短路径代价和最小。Dijkstra算法解决了非负权图中的单源最短路径问题。而A算法则是在Dijkstra的基础上加入了启发式函数h(n)来预估从当前节点到目标节点的代价从而优先探索“看起来更有希望”的节点极大地提高了搜索效率。你可以把A理解为一种“智能的BFS”其核心队列优先队列的出队顺序由f(n) g(n) h(n)决定其中g(n)是从起点到n的实际代价h(n)是预估代价。当h(n)满足“可采纳性”不高估实际代价时A*一定能找到最优解。6.4 记忆化搜索DFS与动态规划的桥梁在一些具有重叠子问题的递归问题中比如斐波那契数列、网格路径计数直接DFS会导致大量重复计算。记忆化搜索通过在递归函数中添加缓存通常是一个字典将已经计算过的子问题结果保存起来下次遇到相同参数时直接返回结果。这本质上是动态规划的自顶向下实现方式将指数级复杂度降到了多项式级别。这是DFS思想一个非常重要的高级应用。7. 常见问题与调试技巧在实际编码和面试中围绕DFS和BFS总会遇到一些典型问题。7.1 问题排查清单现象可能原因解决方案DFS递归深度过大栈溢出图深度太深或存在环路且未标记访问。1. 改用迭代DFS显式栈。2. 检查并确保visited标记逻辑正确。BFS陷入死循环忘记在节点入队时标记visited导致节点被重复加入队列。严格遵守BFS模板在将邻居加入队列前就标记为visited。找到的路径不是最短的错误地使用了DFS来求解最短路径问题。确认问题性质。求最短步数/最少转换次数应首选BFS。算法运行超时搜索空间爆炸未做剪枝或访问标记。1. 检查是否有不必要的重复搜索。2. 考虑使用更高效的数据结构如集合代替列表查重。3. 对于无权图最短路径尝试双向BFS。结果漏掉了一些解回溯时状态恢复不正确影响了其他分支。仔细检查递归DFS中“做选择”和“撤销选择”是否成对出现。7.2 调试与验证技巧小数据测试用最简单的、已知结果的例子测试比如一个3个节点的链式图或一个2x2的网格。打印状态在DFS/BFS的关键步骤如访问节点、将邻居入队/栈时打印出当前状态和数据结构的内容观察其变化是否符合预期。可视化对于网格类问题可以手动在纸上画出网格一步步模拟算法的执行过程这是理解算法行为最有效的方法之一。对比输出对于树的遍历问题DFS前、中、后序和BFS层序的输出顺序是确定的可以用来验证代码正确性。7.3 面试实战要点在技术面试中遇到搜索类题目快速定性首先判断是求所有解还是最优解最短/最小这直接决定使用DFS还是BFS。明确状态定义清楚“节点”是什么可能是棋盘状态、字符串、坐标等以及“边”如何定义如何从一个状态转移到下一个状态。设计访问标记想清楚用什么数据结构集合、数组、位图来记录已访问状态防止重复访问。状态可能需要进行序列化如将元组转为字符串才能存入集合。考虑剪枝在DFS中如果能在递归深入前判断出当前分支不可能得到有效解就提前返回可以大幅提升效率。沟通思路即使最后代码没写完清晰地阐述你选择DFS/BFS的原因、状态的定义和转移方式也能展现你的思维能力。搜索算法是“功在平时”的典型。理解其本质思想掌握清晰的模板再通过大量练习去体会不同场景下的应用和变形你就能在面对复杂的迷宫时心中自有清晰的寻路图。 
长河君 · 2026/8/28 5:34:00 · 阅读 1.2k 深度优先搜索与广度优先搜索：核心思想、代码模板与实战应用
1. 项目概述从“搜索”到“路径”的思维跃迁“搜索”这个词在计算机科学里远不止是你在浏览器里敲几个关键词那么简单。它更像是一个探险家在未知地图上系统性地探索每一个角落直到找到宝藏的过程。而DFS深度优先搜索和BFS广度优先搜索就是这位探险家最基础、也最核心的两种“探险策略”。无论你是刚入门数据结构与算法的新手还是已经工作多年、需要快速回顾核心思想的开发者理解这两种搜索策略就如同掌握了打开“图论”和“状态空间”这两座宝库的万能钥匙。它们不仅是解决“迷宫问题”、“棋盘问题”的理论基础更是构建更复杂算法如A*、Dijkstra的基石。今天我们就抛开枯燥的教科书定义从“为什么需要这两种策略”以及“它们到底解决了什么问题”入手用最贴近实战的视角把DFS和BFS掰开揉碎了讲清楚。2. 核心思想与场景对比深度与广度的哲学在深入代码之前我们必须先理解这两种策略背后的根本逻辑。这决定了你在遇到实际问题时能否第一时间做出正确的选择。2.1 深度优先搜索一条路走到黑DFS的核心思想用一个词概括就是“递归”或“栈”。想象一下你在探索一个巨大的地下洞穴。DFS的策略是选择一条岔路就一直往里走走到尽头碰壁后再退回上一个岔路口选择另一条没走过的路继续深入。它的行为模式是纵向的、深入的。这种策略非常适合解决那些需要遍历所有可能状态或者寻找一条可行路径而非最短路径的问题。比如走迷宫时只要你不在乎走了多少弯路只关心能不能走出去用DFS就非常合适。再比如在排列组合问题中如全排列、子集生成你需要枚举所有可能的情况DFS通过递归可以非常优雅地实现这种“尝试-回溯”的过程。注意DFS在探索过程中如果图或树中存在环路且没有记录已访问状态就会陷入无限循环。因此维护一个visited集合来标记已访问节点是DFS实现中的关键一步。2.2 广度优先搜索层层递进的探索BFS的核心思想则是“队列”。还是那个地下洞穴BFS的策略是你站在起点先把你目光所及一步能到达的所有岔路口都探索一遍记录下这些位置。然后你再从这些新发现的洞口出发探索从它们出发、一步能到达的所有新洞口。如此一层一层地向外扩散。它的行为模式是横向的、层级的。这种策略天然适合求解“最短路径”或“最少步骤”问题。因为BFS保证当它第一次访问到目标节点时所经过的层数即步数一定是最少的。典型的应用场景包括社交网络中查找两个人之间的最短关系链几度分隔、棋盘上骑士走到某个位置的最少步数、单词接龙的最短转换序列等。2.3 决策矩阵我该用DFS还是BFS光知道定义不够关键是要会在实际中选。下面这个表格总结了核心的决策逻辑特性维度深度优先搜索广度优先搜索数据结构栈 (递归调用栈或显式栈)队列遍历顺序深度优先纵向深入广度优先层层推进空间复杂度O(h)h为递归深度/图的最大深度。在树中表现好。O(w)w为图中最宽层的节点数。在稠密图中可能很高。经典适用场景1. 拓扑排序2. 检测图中环3. 寻找连通分量4. 解决所有解问题如八皇后5. 路径存在性判断不要求最短1.无权图的最短路径2. 层次遍历如二叉树层序遍历3. 扩散类问题如腐烂的橘子、岛屿数量4. 状态空间搜索求最优解一个关键比喻探险家认准一条路走到黑不行再回头。广播信号波纹一样从中心一圈圈扩散出去。实操心得很多初学者容易混淆。一个简单的记忆方法是问自己“我要找的是所有可能还是最优最短的那个”。如果是“所有可能”或“是否存在”优先考虑DFS如果是“最短/最少”几乎可以确定用BFS。当然有些问题两者都能解但效率和侧重点不同。3. 算法实现细节与代码模板理解了思想我们来看如何用代码实现。这里我会给出清晰、可复用的模板并解释每一行代码的意图。3.1 深度优先搜索的两种实现方式DFS有两种常见的实现方式递归和显式栈。递归写法简洁体现了DFS“回溯”的本质显式栈则避免了递归深度过大导致的栈溢出问题。递归版DFS模板以图的遍历为例def dfs_recursive(node, visited, graph): :param node: 当前访问的节点 :param visited: 集合记录已访问节点 :param graph: 邻接表表示的图graph[node] 是 node 的邻居列表 # 1. 处理当前节点例如打印、记录路径等 print(node) # 2. 标记当前节点为已访问 visited.add(node) # 3. 遍历当前节点的所有邻居 for neighbor in graph[node]: # 4. 如果邻居未被访问则递归访问 if neighbor not in visited: dfs_recursive(neighbor, visited, graph) # 函数结束自动回溯到上一层调用者显式栈版DFS模板def dfs_iterative(start, graph): visited set() stack [start] # 使用列表模拟栈后进先出 while stack: node stack.pop() # 弹出栈顶元素 if node not in visited: # 处理当前节点 print(node) visited.add(node) # 将邻居压入栈中。注意为了与递归顺序一致假设邻接表是正序 # 可能需要将邻居逆序入栈以保证第一个邻居最后入栈、最先弹出。 for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor)关键点解析递归版的visited.add(node)发生在处理节点之后、遍历邻居之前这能防止重复处理。显式栈版中我们在pop出节点后才检查是否访问这是因为同一个节点可能被多次加入栈中通过不同的父节点我们只在真正处理它时才标记访问避免漏掉某些路径在某些特定问题中。这是DFS实现中一个非常容易出错的细节。3.2 广度优先搜索的队列实现BFS的实现通常使用队列模式非常固定。BFS模板以图的遍历为例from collections import deque def bfs(start, graph): visited set([start]) # 标记起始点已访问 queue deque([start]) # 双端队列高效实现FIFO while queue: # 1. 弹出队列头部节点 node queue.popleft() # 2. 处理当前节点例如如果是找最短路径这里可以判断是否到达目标 print(node) # 3. 遍历当前节点的所有邻居 for neighbor in graph[node]: if neighbor not in visited: # 4. 标记邻居为已访问并加入队列尾部 visited.add(neighbor) queue.append(neighbor)与DFS的关键区别BFS在将邻居加入队列之前就标记为visited。这是因为在BFS中节点一旦被加入队列它迟早会在某一层被处理。如果在popleft时才标记可能导致同一个节点被多个上层节点重复加入队列造成冗余计算甚至在存在环的图中导致无限循环。这个“早标记”是BFS模板的一个铁律。3.3 路径记录如何知道我们是怎么走过来的单纯的遍历节点往往不够我们通常需要记录从起点到目标节点的完整路径。这需要在搜索过程中维护每个节点的“父节点”信息。BFS记录路径的改进模板from collections import deque def bfs_path(start, target, graph): if start target: return [start] queue deque([start]) # parent字典记录每个节点的前驱节点用于回溯路径 parent {start: None} visited set([start]) 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 [] while neighbor is not None: path.append(neighbor) neighbor parent[neighbor] # 向上回溯 return path[::-1] # 反转路径从起点到终点 return None # 未找到路径DFS记录路径在递归DFS中路径隐含在调用栈里。我们可以在递归函数中传递一个path列表在进入节点时加入离开节点时弹出回溯当找到目标时当前的path就是一条可行路径。注意DFS找到的第一条路径不一定是最短的。4. 经典问题实战走迷宫与单词接龙理论结合实战才能融会贯通。我们通过两个LeetCode经典问题来看DFS和BFS如何具体应用。4.1 实战一DFS解迷宫所有路径LeetCode 980. 不同路径 III这个问题是DFS回溯的经典应用在网格中从起点走到终点必须经过每一个空格一次求所有不同路径数。这完美契合了DFS需要探索所有可能状态的特点。解题思路首先遍历网格找到起点(sr, sc)并统计必须经过的空格总数steps_to_do包括终点不包括起点。从起点开始DFS。每次向四个方向移动。维护一个visited集合或直接修改网格为-1来标记已访问防止重复访问。当到达终点时检查已走过的步数是否等于steps_to_do。如果是则找到一条有效路径。回溯在从当前节点返回上层递归前需要撤销访问标记以便其他路径可以再次经过此点。核心代码框架class Solution: def uniquePathsIII(self, grid): rows, cols len(grid), len(grid[0]) start end None steps_to_do 1 # 初始化1会把终点也算进去 # 1. 找到起点、终点并统计必须走的步数 for r in range(rows): for c in range(cols): if grid[r][c] 1: start (r, c) elif grid[r][c] 2: end (r, c) elif grid[r][c] 0: steps_to_do 1 self.answer 0 directions [(0,1), (0,-1), (1,0), (-1,0)] def dfs(r, c, steps_walked): # 2. 终止条件到达终点 if (r, c) end: if steps_walked steps_to_do: self.answer 1 return # 3. 标记当前单元格为已访问用-1表示 temp grid[r][c] grid[r][c] -1 # 4. 遍历四个方向 for dr, dc in directions: nr, nc r dr, c dc # 确保新位置在网格内且是可行走的0或2 if 0 nr rows and 0 nc cols and grid[nr][nc] in (0, 2): dfs(nr, nc, steps_walked 1) # 5. 回溯撤销访问标记 grid[r][c] temp dfs(start[0], start[1], 0) return self.answer避坑技巧在网格DFS中修改原数组进行访问标记是一种节省空间的常用技巧。但务必记得在回溯时恢复原状否则会影响其他分支的搜索。另外将方向数组directions定义为类变量或局部常量比在递归函数内重复创建更高效。4.2 实战二BFS解单词接龙最短路径LeetCode 127. 单词接龙给定一个起始词、一个结束词和一个单词列表每次只能改变一个字母找出从起始词到结束词的最短转换序列长度。这明显是一个“最短路径”问题每个单词是一个节点相差一个字母的单词之间有边用BFS再合适不过。解题思路将单词列表转换为集合word_set便于O(1)时间查询。使用队列进行BFS。队列中的元素可以是(current_word, current_length)。对于队列中的每个单词生成它所有可能的下一个单词即改变每一个位置的字母为a-z检查是否在word_set中或是结束词。为了加速和防止环路一旦一个单词被访问过就将其从word_set中移除这同时起到了visited集合的作用。当弹出的单词等于结束词时返回当前的转换长度。优化点直接生成所有可能的下一跳单词其复杂度是 O(26 * L)其中L是单词长度。这比遍历整个单词列表O(N)来比较每个单词要快得多尤其是在单词列表很大时。核心代码实现from collections import deque class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) - int: word_set set(wordList) if endWord not in word_set: return 0 queue deque([(beginWord, 1)]) # (当前单词 当前路径长度) word_set.discard(beginWord) # 移除起始词避免重复使用 while queue: current_word, current_length queue.popleft() # 如果找到终点返回长度 if current_word endWord: return current_length # 尝试改变当前单词的每一个位置 for i in range(len(current_word)): for c in abcdefghijklmnopqrstuvwxyz: if c current_word[i]: continue # 跳过与原字母相同的改变 next_word current_word[:i] c current_word[i1:] # 如果新单词在集合中说明是有效转换 if next_word in word_set: word_set.remove(next_word) # 关键移除相当于标记已访问 queue.append((next_word, current_length 1)) return 0实操心得在BFS中visited标记的时机至关重要。这里采用了一旦发现新单词就立刻从word_set中移除的策略这保证了每个单词只会被入队一次既防止了环也保证了第一次找到结束词时的路径就是最短的。这是一种非常高效且常见的“就地”访问标记法。5. 性能分析与优化策略理解了基础实现我们还需要知道它们的局限以及如何优化。5.1 时间复杂度与空间复杂度DFS时间复杂度一般为 O(V E)其中V是顶点数E是边数因为每个节点和边最多访问一次。空间复杂度主要取决于递归深度最坏为 O(V)当图退化成一条链时。BFS时间复杂度同样为 O(V E)。空间复杂度则取决于队列中最多同时存放多少节点在最坏情况下如完全二叉树最后一层可能达到 O(V)。一个常见的误解认为DFS一定比BFS省空间。这不一定。在平衡树中BFS的空间复杂度 O(N) 可能大于DFS的 O(logN)但在一个深度很大但宽度很小的图如一条长链中DFS的递归栈空间 O(V) 可能远大于BFS的队列空间 O(1)。需要具体问题具体分析。5.2 栈溢出与迭代深化搜索递归DFS最大的风险是栈溢出。当递归深度过深例如上万层就会触发递归深度限制错误。解决方法有两个改用显式栈的迭代实现如前文所述用自己维护的列表模拟栈通常比系统调用栈能承受的更深。迭代深化搜索这是一种结合了DFS空间优势和BFS最优性优势的算法。它限定一个深度depth在这个深度内进行深度优先搜索。如果没找到目标就将深度限制depth加1重新开始搜索。虽然会重复搜索浅层节点但它的空间复杂度是 O(d)d是目标深度并且能找到最短路径如果路径代价是深度。在状态空间很大、深度未知且要求最优解时IDS是一个不错的选择。5.3 双向BFS大幅缩减搜索空间对于已知起点和终点的最短路径问题双向BFS是性能优化的利器。它从起点和终点同时开始进行BFS。当两个方向的搜索相遇时路径就找到了。为什么更快假设分支因子是b最短路径长度是d。传统BFS需要探索的节点数量级是 O(b^d)。而双向BFS从两头出发理想情况下在中间点相遇每边只需要探索深度约为 d/2 的节点总探索量级约为 O(b^{d/2} b^{d/2}) O(2 * b^{d/2})这比 O(b^d) 指数级地减少了。实现要点使用两个队列或集合分别代表从起点和终点开始的搜索前沿。使用两个字典分别记录从起点和终点到各个节点的距离或路径。每一轮选择节点数较少的那一边进行扩展以平衡两边的搜索进度。当某个节点同时出现在两个已访问集合中时说明相遇路径长度为两边距离之和加1。在单词接龙问题中使用双向BFS可以将性能提升一个数量级。6. 从基础搜索到高级算法DFS和BFS不仅是独立的算法更是构建更复杂算法的组件。理解它们是通向高级图论和搜索算法的必经之路。6.1 拓扑排序DFS的后序遍历拓扑排序用于解决有向无环图的节点线性排序问题使得对于任何有向边 (u, v)u 在排序中都出现在 v 之前。DFS是实现拓扑排序的经典方法对图进行DFS在某个节点的所有邻居都被访问完成后将该节点“后序”加入结果列表最后将结果列表反转即可得到拓扑排序。Kahn算法基于入度则是BFS思想的体现。6.2 连通分量与并查集查找无向图中的连通分量DFS/BFS是最直观的方法从一个未访问的节点开始进行一次完整的DFS或BFS所有能访问到的节点就构成一个连通分量。而并查集则是解决此类问题的另一种高效数据结构它能在近乎常数时间内合并两个集合和查询两个元素是否属于同一集合在某些场景下比搜索更高效。6.3 A*搜索算法启发式引导的BFS当图中的边带有不同的代价或权重时BFS就不再保证找到的是最短路径代价和最小。Dijkstra算法解决了非负权图中的单源最短路径问题。而A算法则是在Dijkstra的基础上加入了启发式函数h(n)来预估从当前节点到目标节点的代价从而优先探索“看起来更有希望”的节点极大地提高了搜索效率。你可以把A理解为一种“智能的BFS”其核心队列优先队列的出队顺序由f(n) g(n) h(n)决定其中g(n)是从起点到n的实际代价h(n)是预估代价。当h(n)满足“可采纳性”不高估实际代价时A*一定能找到最优解。6.4 记忆化搜索DFS与动态规划的桥梁在一些具有重叠子问题的递归问题中比如斐波那契数列、网格路径计数直接DFS会导致大量重复计算。记忆化搜索通过在递归函数中添加缓存通常是一个字典将已经计算过的子问题结果保存起来下次遇到相同参数时直接返回结果。这本质上是动态规划的自顶向下实现方式将指数级复杂度降到了多项式级别。这是DFS思想一个非常重要的高级应用。7. 常见问题与调试技巧在实际编码和面试中围绕DFS和BFS总会遇到一些典型问题。7.1 问题排查清单现象可能原因解决方案DFS递归深度过大栈溢出图深度太深或存在环路且未标记访问。1. 改用迭代DFS显式栈。2. 检查并确保visited标记逻辑正确。BFS陷入死循环忘记在节点入队时标记visited导致节点被重复加入队列。严格遵守BFS模板在将邻居加入队列前就标记为visited。找到的路径不是最短的错误地使用了DFS来求解最短路径问题。确认问题性质。求最短步数/最少转换次数应首选BFS。算法运行超时搜索空间爆炸未做剪枝或访问标记。1. 检查是否有不必要的重复搜索。2. 考虑使用更高效的数据结构如集合代替列表查重。3. 对于无权图最短路径尝试双向BFS。结果漏掉了一些解回溯时状态恢复不正确影响了其他分支。仔细检查递归DFS中“做选择”和“撤销选择”是否成对出现。7.2 调试与验证技巧小数据测试用最简单的、已知结果的例子测试比如一个3个节点的链式图或一个2x2的网格。打印状态在DFS/BFS的关键步骤如访问节点、将邻居入队/栈时打印出当前状态和数据结构的内容观察其变化是否符合预期。可视化对于网格类问题可以手动在纸上画出网格一步步模拟算法的执行过程这是理解算法行为最有效的方法之一。对比输出对于树的遍历问题DFS前、中、后序和BFS层序的输出顺序是确定的可以用来验证代码正确性。7.3 面试实战要点在技术面试中遇到搜索类题目快速定性首先判断是求所有解还是最优解最短/最小这直接决定使用DFS还是BFS。明确状态定义清楚“节点”是什么可能是棋盘状态、字符串、坐标等以及“边”如何定义如何从一个状态转移到下一个状态。设计访问标记想清楚用什么数据结构集合、数组、位图来记录已访问状态防止重复访问。状态可能需要进行序列化如将元组转为字符串才能存入集合。考虑剪枝在DFS中如果能在递归深入前判断出当前分支不可能得到有效解就提前返回可以大幅提升效率。沟通思路即使最后代码没写完清晰地阐述你选择DFS/BFS的原因、状态的定义和转移方式也能展现你的思维能力。搜索算法是“功在平时”的典型。理解其本质思想掌握清晰的模板再通过大量练习去体会不同场景下的应用和变形你就能在面对复杂的迷宫时心中自有清晰的寻路图。