1. 从“迷宫寻路”到“状态转移”两种经典搜索模型的深度拆解在算法竞赛和日常开发中遇到需要“找一条路”或者“找一种操作序列”的问题我们第一时间想到的往往是深度优先搜索DFS或广度优先搜索BFS。但同样是搜索面对不同的问题模型我们的思考路径和代码实现会有天壤之别。今天我们不谈宽泛的搜索框架而是聚焦于DFS在两种最经典、也最易混淆的模型中的应用连通性模型和最小步数模型。很多朋友在刷题时会有这样的困惑同样是走迷宫为什么有的题用DFS递归几下就出来了有的题却必须用BFS或者用DFS迭代加深其核心区别就在于问题到底属于哪种模型。连通性模型关心的是“能否到达”或者“所有能到达的点”它探索的是一片“区域”而最小步数模型关心的是“最快多久能到”它寻找的是一条“最短路径”。虽然DFS在两种模型中都有应用但其目的、写法和优化方向截然不同。理解这两种模型不仅能帮你快速判断题目类型选择合适的方法更能让你在实现DFS时清晰地知道每一步在做什么为什么要这样设计状态以及如何避免那些常见的坑比如爆栈、重复访问、效率低下。接下来我们就结合具体的场景和代码把这两个模型掰开揉碎了讲清楚。2. 连通性模型探索与标记的“地毯式扫描”连通性模型顾名思义核心任务是判断或找出图中连通的组成部分。这里的“图”是广义的可以是二维网格地图、人际关系网也可以是抽象的状态关系。DFS在这种模型下的角色就像一个带着油漆的探索者从起点开始尽可能深地走遍所有能走通的路径并把走过的区域都标记上颜色最终所有被染上同一种颜色的区域就属于同一个连通块。2.1 核心问题与DFS的天然适配性连通性模型通常要回答以下几类问题可达性判断点A和点B是否连通例如迷宫起点能否走到终点连通块计数图中有多少个互不连通的子图例如计算岛屿数量。连通块信息统计每个连通块的大小、周长、属性总和是多少连通分量提取找出所有属于同一个连通块的节点。DFS的递归“一路走到黑再回头”的特性非常适合完成这种“探索并标记整个区域”的任务。它不在乎走了多少“步”只在乎“有没有走过”。递归的栈空间恰好用来记录当前的探索路径。2.2 经典场景实战统计网格中的岛屿数量这是最经典的连通性模型问题LeetCode 200。给定一个由1陆地和0水组成的二维网格计算岛屿的数量。岛屿被水包围并且通过水平或垂直方向相邻的陆地连接而成。DFS思路解析 我们遍历网格的每一个单元格。当遇到一块未被访问的陆地1时就将其作为一个新岛屿的起点启动一次DFS。这次DFS的任务是“淹没”整个岛屿将当前陆地标记为已访问比如改为0然后向其四个方向上、下、左、右递归探索。递归会一直进行直到当前岛屿的所有陆地都被“淹没”。这样一次DFS调用就探索完了一个完整的连通块。主循环中启动DFS的次数就是岛屿的数量。关键代码实现与细节def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) count 0 def dfs(r, c): # 递归终止条件越界、遇到水、或已访问过 if r 0 or r rows or c 0 or c cols or grid[r][c] ! 1: return # 标记当前陆地已访问 grid[r][c] 0 # 向四个方向递归探索 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: # 发现新岛屿启动DFS探索整个岛屿 dfs(r, c) count 1 return count为什么这样写—— 设计逻辑拆解原地修改标记直接修改原数组为0省去了额外的visited数组空间。这是连通性模型的常见技巧前提是允许修改输入数据。递归方向顺序上下左右的顺序无关紧要因为目标是遍历整个区域任何顺序最终都能覆盖全图。递归深度递归深度等于岛屿中陆地单元格的数量。对于非常大的岛屿可能存在递归栈溢出的风险Python默认递归深度约1000。这是DFS在连通性模型中的一个主要局限。时间复杂度O(rows * cols)每个单元格最多被访问一次。注意这里有一个初学者极易混淆的点。虽然这个问题叫“岛屿数量”我们也是在网格上移动但它不是最小步数模型。我们并不关心从一个1走到另一个1需要多少步我们只关心哪些1是连成一体的。所以DFS在这里是深度优先的“涂色”而不是寻找最短路径。2.3 连通性模型的DFS实现要点与避坑指南基于上面的例子我们可以总结出连通性模型DFS的通用模板和注意事项通用模板框架主函数遍历所有可能的起点如网格的每个格子、图的每个节点。判断起点如果当前点符合条件如未访问、是陆地且是新的连通分量起点则启动DFS。DFS递归函数参数当前状态如坐标(r, c)。终止条件越界、不满足条件是墙、是水、已访问。处理当前状态标记为已访问可能进行一些统计如面积1。递归扩展向所有可能的方向邻接状态进行递归调用。常见“坑”与解决方案栈溢出当连通块非常大时例如10^5个节点的一条链递归DFS会导致调用栈过深而溢出。解决方案使用栈Stack进行迭代式的DFS或者使用BFS。迭代DFS同样使用栈但使用的是堆内存通常比调用栈深得多。def dfs_iterative(start_r, start_c): stack [(start_r, start_c)] while stack: r, c stack.pop() if 越界或不满足条件: continue 标记访问并处理 # 将邻接点压栈注意顺序可能影响遍历次序但不影响连通性结果 for dr, dc in directions: stack.append((rdr, cdc))忘记标记访问状态这是最致命的错误会导致在环状路径中无限递归。必须在进入递归函数后立即标记而不是在递归调用前。因为从不同路径可能到达同一点如果在调用前判断可能多个分支都认为该点可访问从而重复入栈。方向数组的使用对于网格问题使用方向数组directions [(1,0), (-1,0), (0,1), (0,-1)]可以让代码更清晰避免写四行重复的递归调用。3. 最小步数模型寻找最优解的“探路者”最小步数模型的目标非常明确找到从初始状态变换到目标状态所需的最少操作步骤。这里的“状态”可以是一个点在迷宫中的位置也可以是一个魔方的排列或者一个数字经过特定运算后的值。DFS在这个模型中的应用更像是一个执着但可能走弯路的探险家它尝试所有可能的操作序列路径并记录下最短的那个。3.1 为何DFS在求“最小”时显得笨拙DFS的本质是深度优先它会沿着一条分支一直走到头遇到死胡同或目标然后回溯尝试其他分支。对于求最小步数它存在天然缺陷首次找到的不一定最短DFS可能沿着一条很长的路径早早找到了目标但这条路径可能不是最短的。DFS无法像BFS那样保证首次找到的就是最优解。需要全局比较为了找到最小步数DFS必须探索所有可能的路径或通过剪枝避免一些然后比较它们的长度。这可能导致指数级的时间复杂度。那么什么时候会用DFS来解决最小步数问题呢主要有两种情况状态空间非常小或者路径长度有明确上限可以承受全搜索。使用迭代加深搜索IDS这是一种结合了DFS空间效率和BFS最优性特性的算法我们稍后会详细讲。3.2 经典场景实战骑士移动的最短步数问题在一个8x8的国际象棋棋盘上给定骑士的起点(sx, sy)和终点(tx, ty)。骑士走“日”字即先沿一格直线再沿一格对角线。求骑士到达目标位置所需的最少步数。分析这是一个典型的最短路径问题在无权图上BFS是首选因为它能保证首次到达时的路径就是最短的。但我们先用最朴素的DFS思路来理解这个模型看看它会遇到什么问题。朴素DFS思路不推荐仅用于理解模型 从起点开始骑士有8个可能的移动方向。DFS会选择其中一个方向走一步然后递归地继续走。我们需要记录当前步数当到达终点时更新全局的最小步数。同时必须用一个visited集合或数组来记录已经访问过的位置避免在环里打转但注意在求最短路径时简单地标记“已访问”可能会错过更优路径这是DFS用于求最短路径的另一个难点。问题暴露如果棋盘很大状态空间爆炸。即使有visited简单的DFS也可能因为访问顺序问题错过从另一条路以更少步数到达同一点的机会。例如从A到B有两条路一条5步一条3步。DFS可能先走了5步的路径到了B并标记为已访问之后当3步的路径尝试访问B时会因为B已被访问而直接返回从而错过了更优解。因此在DFS求最短路径时visited数组通常需要记录到达该状态时的步数如果新的路径步数更少则需要更新并重新搜索。这实质上变成了记忆化搜索或Dijkstra算法的变种复杂度上升。BFS解决方案作为对比from collections import deque def minKnightMoves(x, y): # 简化问题只考虑第一象限利用对称性 x, y abs(x), abs(y) # 骑士的8个移动方向 moves [(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)] queue deque([(0, 0, 0)]) # (x, y, steps) visited set() visited.add((0,0)) while queue: cur_x, cur_y, steps queue.popleft() if cur_x x and cur_y y: return steps for dx, dy in moves: nx, ny cur_x dx, cur_y dy # 一个简单的边界和访问判断实际可以更宽松 if (nx, ny) not in visited and -2 nx x2 and -2 ny y2: visited.add((nx, ny)) queue.append((nx, ny, steps1)) return -1BFS保证了当我们第一次从队列中取出目标坐标时对应的步数就是最短步数。3.3 迭代加深搜索IDS让DFS拥有BFS的“最优性”既然BFS好为什么还要提DFS因为BFS的空间复杂度是O(b^d)其中b是分支因子d是目标深度。当解在很浅的深度但分支因子很大时BFS的队列可能会消耗巨大内存。而DFS的空间复杂度是O(d)。迭代加深搜索Iterative Deepening Search, IDS结合了两者的优点外层循环逐渐增加搜索深度限制max_depth从0, 1, 2, ... 逐步增加。内层搜索在当前的max_depth限制下执行深度优先搜索DFS。如果搜索过程中步数超过max_depth则剪枝返回。过程当max_depth小于实际最短路径长度时DFS会搜索整个深度为max_depth的树但找不到解。然后max_depth加1再次进行DFS。虽然看起来重复搜索了浅层节点但因为在搜索树中深层节点数量远多于浅层节点所以这种重复的代价相对较小。IDS解决骑士移动问题的框架def ids_knight(start, target): def depth_limited_dfs(node, depth, max_depth, visited): if node target: return True if depth max_depth: return False for move in moves: next_node apply_move(node, move) if next_node not in visited: visited.add(next_node) if depth_limited_dfs(next_node, depth1, max_depth, visited): return True visited.remove(next_node) # 回溯 return False for max_depth in range(0, SOME_UPPER_BOUND): visited set([start]) if depth_limited_dfs(start, 0, max_depth, visited): return max_depth return -1IDS的优势与代价优势空间复杂度低O(d)总能找到最短路径具备完备性和最优性。代价时间上由于重复搜索复杂度约为O(b^d)比BFS的O(b^d)稍差一个常数因子但通常可以接受。对于分支因子大、深度未知的问题IDS是比朴素DFS和BFS更折中、更可靠的选择。4. 两种模型的本质区别与选用决策树通过前面的分析我们可以从以下几个维度来区分连通性模型和最小步数模型特性维度连通性模型最小步数模型核心目标判断连通性、统计连通块信息找到初始状态到目标状态的最少操作次数搜索目的遍历一个连通区域的所有节点寻找一条长度最短的路径解的特征可能有多解所有连通节点或布尔解是否连通通常求一个最优解最小步数DFS的角色直接、自然的工具用于探索和标记需要配合策略如迭代加深、剪枝、记忆化来寻找最优解访问标记标记“是否访问过”防止重复遍历同一区域标记时需小心可能需记录“到达该状态的最优步数”以免错过更优路径典型问题岛屿数量、迷宫可达性、朋友圈并查集更优骑士移动、八数码、单词接龙最短序列首选算法DFS / BFS (均可DFS代码常更简洁)BFS (无权图)/Dijkstra (带权图)/A(有启发函数)* /IDS (状态空间大时省内存)如何根据问题快速选择模型问自己两个问题问题问的是“有没有”、“哪些所有”还是“最少多少步”如果是“起点和终点是否连通”“有多少个孤立的群体”这是连通性模型。如果是“最少需要多少步从A到B”“最少需要多少次操作变成目标状态”这是最小步数模型。在最小步数模型下如何选择具体算法状态空间小DFS全搜索或BFS均可。状态空间大且求无权图最短路径优先BFS。它保证最优且通常不慢。状态空间巨大担心BFS内存爆炸考虑迭代加深搜索IDS。状态转移有代价带权图使用Dijkstra算法。有良好的启发式评估函数可以考虑A*搜索。5. 混合模型与进阶技巧当问题变得复杂实际比赛中问题不会总是那么纯粹。有时一个问题是两种模型的结合或者需要更精巧的DFS设计。案例带有连通性判断的最小步数问题“滑动谜题”LeetCode 773是一个很好的例子。在一个2x3的棋盘上有5个带数字的方块和一个空格。每次操作可以将一个与空格相邻的方块滑入空格。给定初始状态问需要至少多少次移动才能达到目标状态[[1,2,3],[4,5,0]]。分析它是最小步数模型因为要求“最少移动次数”。状态是什么是整个棋盘的布局可以编码为一个字符串如123450。如何搜索从初始状态开始每次操作空格与上下左右交换生成新的状态。这形成了一个状态图。连通性体现在哪我们需要判断从初始状态是否能到达目标状态。在这个问题中由于状态空间是有限的且所有状态在操作下是连通的对于标准2x3谜题所以一定是可达的。但对于某些初始状态可能需要先判断是否可解这涉及到更深的数学性质排列的逆序数奇偶性。解决方案 这明显是一个最短路径问题。状态是棋盘排列边是每次移动。由于是无权图BFS是标准解法。我们使用队列从初始状态开始每次取出一个状态生成其所有可能的下一状态即空格移动后的新排列如果没访问过就加入队列并记录步数。首次遇到目标状态时步数即为答案。DFS在这里能用吗可以但效率低且不能保证首次找到最优。我们可以用IDS但BFS更直观高效。这个例子说明了即使问题背后隐含着状态空间的连通性但只要核心发问是“最少步数”我们就应该按照最小步数模型的优选算法BFS来解题。DFS的进阶优化剪枝与记忆化在复杂的DFS搜索中尤其是最小步数模型的变种如求所有方案或在一定限制下找方案剪枝至关重要。可行性剪枝当前状态已经不可能达到目标提前返回。例如在搜索和为目标值的组合时如果当前和已经大于目标值就没必要继续搜索了。最优性剪枝如果当前路径的代价已经超过了目前已知的最优解提前返回。记忆化搜索Memoization对于会重复到达的子状态将计算结果缓存起来。这通常用于解决重叠子问题将指数级复杂度降为多项式级别。例如在“不同路径”问题中从(i,j)到终点的路径数是一个固定值我们可以用memo[i][j]存储避免重复计算。6. 从理论到代码编写健壮DFS的实用经验无论是哪种模型写出正确、高效的DFS代码都需要注意以下几点这些是我在无数次调试中总结出的血泪教训1. 状态表示要唯一且简洁状态是搜索的基本单元。在连通性模型里状态可能就是坐标(x, y)。在最小步数模型里状态可能是一个复杂的结构如棋盘、字符串。务必将其转化为可以哈希的类型如元组、字符串、整数编码以便放入visited集合或用于记忆化。例如二维棋盘可以压扁成字符串。2. 访问标记的时机是生死线标记一定要在“处理该状态”的同一时间进行最好是在递归函数入口或刚从队列中取出后立即标记。绝对不要在递归调用后再标记否则极易导致重复访问和栈溢出。对于BFS在节点入队时标记是更安全的做法可以保证同一层级不会重复入队同一个节点。3. 递归深度与系统栈限制Python默认递归深度约1000。对于深度可能很大的搜索有几种选择改用迭代DFS显式栈。改用BFS队列。修改递归深度限制sys.setrecursionlimit(1000000)但这只是权宜之计可能引发C栈溢出。使用迭代加深搜索IDS它天然限制了深度。4. 方向遍历的写法对于网格类的DFS使用方向数组是最佳实践。它使代码清晰易于修改例如改为8方向。# 四方向 dirs [(0,1), (0,-1), (1,0), (-1,0)] for dx, dy in dirs: nx, ny x dx, y dy # ... 判断和递归5. 回溯的处理在需要记录路径而不仅仅是步数或者状态需要恢复如排列组合问题时需要进行回溯。visited.add(state) path.append(state) dfs(next_state) path.pop() # 回溯移除当前选择 # visited.remove(state) # 注意通常全局visited不需要回溯除非是寻找所有路径且允许重复访问节点是否需要从visited中remove取决于问题定义。在寻找所有可能路径而不是仅仅判断是否存在时通常需要在递归返回后remove以允许其他路径再次访问该节点。但在单纯判断连通性或最短路径时通常不需要。6. 输入边界检查永远不要相信输入数据。在访问数组前先检查下标是否越界。这是避免运行时错误的最基本保障。最后理解连通性模型和最小步数模型是掌握搜索算法的关键一步。它们代表了搜索的两个根本性目的探索空间和寻找最优路径。下次当你面对一个搜索问题时先停下来花30秒分析它属于哪种模型再选择合适的算法和实现策略这将让你事半功倍避免在错误的方向上浪费大量调试时间。