1. 从一笔画问题到算法核心为什么我们需要深度优先搜索最近在社区里看到一个挺有意思的题目一个7*5的格子如何遍历所有格子一笔联通第二行左1格和第四行右1格这本质上就是一个路径搜索问题。很多朋友的第一反应可能是手动尝试画来画去但格子稍微大一点或者规则复杂一些手动枚举就几乎不可能了。这正是算法特别是像深度优先搜索DFS这类图遍历算法大显身手的地方。DFS不是什么高深莫测的黑科技它就是一种“一条道走到黑碰壁再回头”的朴素策略但正是这种策略解决了我工作中无数次的路径查找、状态枚举和连通性分析问题。简单来说DFS是一种用于遍历或搜索树或图的算法。它的核心思想是尽可能深地探索图的分支当一条路径走到尽头即遇到叶子节点或已访问节点时就回溯到上一个分岔口选择另一条未探索的路径继续深入。这个过程听起来是不是很像我们走迷宫时的策略先沿着一条路一直走直到死胡同然后退回到上一个岔路口换条路再试。这个算法之所以重要是因为它构成了许多更复杂算法的基础比如拓扑排序、寻找连通分量、解决迷宫问题、以及回溯法解决八皇后、数独等约束满足问题。对于初学者可能会把它和广度优先搜索BFS搞混。BFS是“层层推进”像水波纹扩散适合找最短路径而DFS是“钻探到底”更适合探索所有可能或者需要递归回溯的场景。理解DFS不仅仅是记住它的代码模板更是要理解其“递归”或“栈”的本质以及它如何系统地枚举状态空间。接下来我们就从它的工作原理、具体实现、再到实际应用和那些容易踩的坑把它彻底讲透。2. DFS的工作原理递归与栈的双重视角要理解DFS必须从两个层面来看一是直观的递归过程它最符合人类“探索-回溯”的思维模式二是显式的栈操作它揭示了算法的底层机制。两者等价但适用场景略有不同。2.1 递归视角自然的探索与回溯递归实现DFS是最直观的。我们可以把图或树的遍历看作一个任务访问当前节点然后对于它的每一个未访问的邻居重复这个任务。这个过程天然地形成了深度优先。以一个简单的无向图为例假设我们有节点A、B、C、D连接关系为A-B, A-C, B-D。从A开始DFS访问A标记A为已访问。处理A的第一个邻居B顺序取决于存储结构。递归进入B。访问B标记B为已访问。处理B的邻居。B的邻居有A和D。A已访问跳过。递归进入D。访问D标记D为已访问。D没有其他未访问邻居递归函数开始返回回溯。回溯到B处B的所有邻居处理完毕继续回溯到A。在A处处理下一个未访问邻居C。访问C标记C为已访问。C没有未访问邻居回溯到A。A的所有邻居处理完毕整个遍历结束。顺序是 A - B - D - C。你会发现算法确实是一条路先走到了底A-B-D然后才回头访问C。递归的代码模板非常简洁以图的邻接表存储为例def dfs_recursive(node, visited, graph): if node in visited: return # 处理当前节点例如打印 print(node) visited.add(node) # 标记已访问 # 递归探索所有邻居 for neighbor in graph[node]: dfs_recursive(neighbor, visited, graph) # 初始化 visited set() graph { A: [B, C], B: [A, D], C: [A], D: [B] } dfs_recursive(A, visited, graph)递归的优点是代码清晰与DFS的逻辑定义高度一致。但它有一个潜在的缺点递归深度受系统栈空间限制。对于深度可能很大的图比如一条长长的链递归可能导致栈溢出错误。2.2 栈视角显式管理探索路径栈视角将递归隐式使用的系统调用栈替换为我们自己维护的一个显式栈。这让我们对遍历过程有更强的控制力也避免了递归深度限制的问题。算法步骤如下将起始节点压入栈并标记为已访问。当栈不为空时弹出栈顶节点作为当前节点。处理当前节点如访问。将当前节点的所有未访问邻居节点压入栈中并标记为已访问。重复步骤2-4。这里有一个关键细节在第4步我们需要在将邻居压栈的同时就标记为已访问而不是等弹出时再标记。为什么因为同一个节点可能会被多个不同的父节点在步骤4中尝试压入栈中。如果等弹出时才标记那么这个节点可能会在栈中出现多次导致被重复处理严重时甚至导致无限循环对于无向图尤其如此。还是以之前的图为例用栈来实现栈初始化:[A], visited:{A}弹出A处理A。A的邻居B、C均未访问将它们压栈并标记。栈:[B, C], visited:{A, B, C}弹出C处理C。C的邻居A已访问无操作。栈:[B]弹出B处理B。B的邻居A已访问、D未访问。将D压栈并标记。栈:[D], visited:{A, B, C, D}弹出D处理D。D的邻居B已访问。栈:[]遍历结束。顺序是 A - C - B - D。注意这个顺序和递归版本A-B-D-C不同这是因为栈是“后进先出”我们压入邻居的顺序是B、C假设按字母顺序但弹出时是C先于B。这说明了DFS的遍历顺序并不唯一它取决于邻居的访问顺序图的存储结构。但“深度优先”的特性是不变的它总是优先处理最新发现的节点。栈实现的代码def dfs_iterative(start, graph): visited set() stack [start] visited.add(start) # 入栈即标记 while stack: node stack.pop() print(node) # 处理当前节点 # 注意这里为了得到和递归类似的邻接顺序可能需要逆序压栈 # 因为栈是LIFO如果想先处理graph[node]的第一个邻居就要最后压入它。 for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor) visited.add(neighbor) # 关键入栈时标记 dfs_iterative(A, graph)注意在迭代栈实现中“入栈时标记已访问”是避免重复访问和死循环的铁律。这是新手最容易出错的地方之一。3. DFS的代码实现与时空复杂度分析掌握了原理我们来看看具体的代码实现模板并分析其性能。DFS的复杂度分析相对直观但有一些边界条件需要注意。3.1 针对不同数据结构的实现模板1. 二叉树的DFS遍历二叉树是图的特例每个节点最多有两个子节点左、右。其DFS遍历根据访问根节点的顺序分为前序、中序、后序。这是面试中的经典问题。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 递归模板以前序遍历为例 def preorder_traversal(root): result [] def dfs(node): if not node: return result.append(node.val) # 前序根左右 dfs(node.left) dfs(node.right) dfs(root) return result # 迭代模板使用栈模拟 def preorder_traversal_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 栈是LIFO所以先右后左保证弹出时是先左后右 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result中序和后序的迭代实现需要更巧妙的栈操作或标记法核心思想依然是利用栈来回溯。2. 图的DFS遍历邻接表前面已经给出了递归和迭代的模板。对于大规模图迭代栈版本通常更安全。如果需要记录路径比如开头的“一笔画”问题栈中就不能只存节点可以存(当前节点, 当前路径)这样的元组。3. 网格二维矩阵的DFS这类问题非常常见比如“岛屿数量”、“单词搜索”。网格可以看作一个图每个格子是一个节点与上下左右四个格子相邻。def dfs_grid(grid, i, j, visited): # 边界条件判断 if i 0 or i len(grid) or j 0 or j len(grid[0]): return # 业务逻辑判断如是否已访问、是否是障碍物等 if visited[i][j] or grid[i][j] 0: return # 处理当前格子 visited[i][j] True # 或者直接修改原grid如 grid[i][j] # # 递归探索四个方向 dfs_grid(grid, i-1, j, visited) # 上 dfs_grid(grid, i1, j, visited) # 下 dfs_grid(grid, i, j-1, visited) # 左 dfs_grid(grid, i, j1, visited) # 右这种“沉没岛屿”式的DFS是解决许多二维矩阵连通性问题的利器。3.2 时间复杂度与空间复杂度时间复杂度DFS必须访问图中的每一个节点和每一条边在邻接表表示下。因此对于图G(V, E)其时间复杂度为O(|V| |E|)。其中|V|是顶点数|E|是边数。对于树这种特殊的图边数|E| |V| - 1复杂度就是 O(|V|)。对于网格m x n每个节点有最多4条边总节点数|V| m*n总边数|E| ≈ 4*m*n忽略边界所以复杂度也是 O(m*n)。空间复杂度空间消耗主要来自两部分已访问标记需要一个visited集合或数组空间为 O(|V|)。递归栈或显式栈在最坏情况下比如图是一条深度为|V|的链递归深度或栈的大小就是 O(|V|)。因此总的空间复杂度为O(|V|)。这里有一个重要的实操心得当图非常深时递归DFS可能导致“递归深度超出限制”的错误。例如在Python中默认递归深度约为1000。处理上万节点的链式结构时必须使用迭代显式栈的DFS。迭代栈的空间复杂度理论最坏情况也是O(|V|)但在实践中我们通常可以手动设置一个更大的栈如果语言支持或者使用迭代方法避免系统栈的限制。4. DFS的核心应用场景与实战拆解理解了原理和实现我们来看看DFS能解决哪些实际问题。它的应用远超简单的遍历更是许多高级算法思想的载体。4.1 路径查找与连通性问题这是DFS最直接的应用。文章开头提到的“7*5格子一笔画”问题就是一个典型的路径查找需要找到一条访问所有格子的哈密顿路径。虽然DFS不一定能找到最优解如最短路径但它能系统地枚举所有可能路径。实战案例迷宫求解给定一个二维矩阵表示迷宫0代表路1代表墙从起点(0,0)到终点(m-1, n-1)找出一条可行路径。def solve_maze(maze, start, end): directions [(-1,0), (1,0), (0,-1), (0,1)] # 上下左右 path [] visited set() def dfs(current): if current end: return True # 找到路径 x, y current for dx, dy in directions: nx, ny x dx, y dy next_pos (nx, ny) # 检查边界、是否可走、是否访问过 if 0 nx len(maze) and 0 ny len(maze[0]) and maze[nx][ny] 0 and next_pos not in visited: visited.add(next_pos) path.append(next_pos) if dfs(next_pos): # 递归探索 return True # 回溯这条路径走不通撤销选择 path.pop() return False visited.add(start) path.append(start) if dfs(start): return path else: return None这个例子清晰地展示了DFS在回溯法中的应用做出选择走向一个邻居递归探索如果失败则撤销选择path.pop()并尝试其他选项。连通分量计数岛屿问题LeetCode经典题目“200. 岛屿数量”。目标是统计网格中被‘水’‘0’包围的‘陆地’‘1’块数。DFS的思路是遍历每个格子如果遇到未访问的‘1’就以它为起点进行DFS将相连的所有‘1’标记为已访问这样一次DFS就“沉没”了一个岛屿同时计数加一。def numIslands(grid): if not grid: return 0 count 0 m, n len(grid), len(grid[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or grid[i][j] ! 1: return grid[i][j] # # 标记为已访问替代visited数组 dfs(i1, j) dfs(i-1, j) dfs(i, j1) dfs(i, j-1) for i in range(m): for j in range(n): if grid[i][j] 1: dfs(i, j) count 1 return count这里用了一个小技巧直接修改原数组grid[i][j] #来替代额外的visited数组节省了空间。这是处理网格DFS时常用的优化手段。4.2 回溯法枚举所有可能解回溯法是DFS在状态空间搜索上的直接体现用于解决组合、排列、子集、数独、N皇后等需要尝试所有可能性的问题。其核心框架就是DFS在每一层做一个选择进入下一层递归如果最终状态不满足条件则回溯到上一层撤销选择尝试下一个选项。实战案例全排列问题给定一个不含重复数字的数组返回其所有可能的全排列。def permute(nums): res [] n len(nums) def backtrack(path, used): # 终止条件路径长度等于原数组长度 if len(path) n: res.append(path[:]) # 注意深拷贝 return for i in range(n): if not used[i]: # 数字未被使用 # 做选择 used[i] True path.append(nums[i]) # 进入下一层决策树 backtrack(path, used) # 撤销选择回溯 path.pop() used[i] False backtrack([], [False]*n) return res这个模板是回溯法的经典范式几乎可以套用到所有类似问题上。path记录当前选择used记录使用状态for循环枚举当前层的所有选项递归调用进入下一层递归返回后通过pop()和False进行回溯。4.3 拓扑排序与环检测拓扑排序是针对有向无环图DAG的顶点进行线性排序使得对于任何有向边u-vu在排序中都出现在v之前。DFS是实现拓扑排序的常用方法之一。算法过程DFS后序遍历逆序对图进行DFS遍历。在某个节点的所有邻居都被访问完成后即递归函数即将返回时将该节点加入一个栈中。DFS结束后将栈中元素依次弹出得到的序列就是拓扑排序的一个结果。为什么因为后序遍历保证了父节点依赖项总是在子节点被依赖项之后被加入栈而栈的LIFO特性反转了这个顺序使得父节点先于子节点弹出。def topological_sort_dfs(numCourses, prerequisites): # 构建邻接表 graph [[] for _ in range(numCourses)] for dest, src in prerequisites: graph[src].append(dest) visited [0] * numCourses # 0未访问1访问中2已访问 result_stack [] has_cycle False def dfs(node): nonlocal has_cycle if has_cycle: return visited[node] 1 # 标记为“访问中” for neighbor in graph[node]: if visited[neighbor] 0: dfs(neighbor) elif visited[neighbor] 1: # 遇到“访问中”的节点说明存在环 has_cycle True return visited[node] 2 # 标记为“已访问完成” result_stack.append(node) # 后序位置入栈 for i in range(numCourses): if visited[i] 0 and not has_cycle: dfs(i) if has_cycle: return [] # 有环图无法拓扑排序 return result_stack[::-1] # 栈逆序即为拓扑排序结果这个实现还顺带完成了环检测。visited状态为1访问中表示节点在当前的递归栈上如果DFS过程中遇到了状态为1的邻居说明存在一条从邻居回到当前节点的边即存在环。这是判断有向图是否有环的高效方法。5. DFS的优化、变体与常见陷阱虽然DFS框架清晰但在实际应用中不经优化的朴素DFS可能会效率低下甚至无法工作。这里分享几个关键的优化方向和容易踩的坑。5.1 剪枝避免无效搜索的利器在回溯或状态空间搜索中很多路径在走到一半时就已经能判断不可能到达终点了。继续深入就是浪费时间。剪枝就是在递归树的节点上提前判断并终止不可能产生结果的搜索分支。实战案例组合总和问题给定候选数组和一个目标数找出所有和为目标的组合数字可重复使用。如果不对搜索树进行剪枝复杂度会爆炸。def combinationSum(candidates, target): res [] candidates.sort() # 排序是剪枝的前提 n len(candidates) def backtrack(start, path, remaining): if remaining 0: res.append(path[:]) return for i in range(start, n): # 关键剪枝如果当前数字已经大于剩余目标由于数组已排序后面的数字更大直接break if candidates[i] remaining: break # 剪枝 path.append(candidates[i]) # 注意下一层递归的start仍然是i因为数字可以重复使用 backtrack(i, path, remaining - candidates[i]) path.pop() backtrack(0, [], target) return res这里的剪枝条件if candidates[i] remaining: break极大地减少了搜索空间。排序使得我们可以利用“当前数太大后面的数更大”这一信息提前终止循环。这是回溯问题中非常经典的“排序剪枝”优化。5.2 记忆化搜索应对重叠子问题在一些DFS问题中可能会重复计算相同的子状态。例如在计算斐波那契数列时fib(n) fib(n-1) fib(n-2)递归树中有大量重复节点。记忆化搜索Memoization通过一个缓存通常是字典或数组来存储已经计算过的子问题的结果当再次遇到相同子问题时直接返回缓存结果避免重复递归。实战案例网格中的不同路径带障碍物LeetCode “63. 不同路径 II”。机器人从左上角到右下角只能向右或向下走网格中有障碍物。求路径数。 朴素DFS会超时因为存在大量重复计算dfs(i, j)。def uniquePathsWithObstacles(grid): m, n len(grid), len(grid[0]) memo [[-1] * n for _ in range(m)] # 记忆化数组 def dfs(i, j): # 越界或遇到障碍物 if i m or j n or grid[i][j] 1: return 0 # 到达终点 if i m-1 and j n-1: return 1 # 查缓存 if memo[i][j] ! -1: return memo[i][j] # 计算并缓存 memo[i][j] dfs(i1, j) dfs(i, j1) return memo[i][j] return dfs(0, 0)记忆化搜索是动态规划DP的递归形式。它保留了DFS思路清晰的优点又通过缓存避免了指数级重复计算。当问题具有“最优子结构”和“重叠子问题”时记忆化搜索是首选优化。5.3 迭代深化深度优先搜索IDDFS这是一种结合了DFS空间效率和BFS能找最短路径在边权相等时优势的算法。它通过逐渐增加深度限制来进行多次DFS。设置深度限制depth_limit 0。执行深度限制为depth_limit的DFS只探索深度不超过depth_limit的节点。如果找到目标结束否则depth_limit 1回到步骤2。IDDFS常用于状态空间很大、且目标深度未知的搜索问题如某些 puzzles。它避免了BFS需要存储整层节点的空间开销O(b^d)b为分支因子d为深度也避免了DFS可能陷入很深的无用分支。其时间复杂度与BFS相同O(b^d)空间复杂度仅为O(d)。5.4 那些年我踩过的坑与注意事项忘记标记已访问Visited Array/Set这是最最常见的错误会导致无限递归和栈溢出。尤其是在无向图中A访问BB又会访问A形成死循环。牢记在进入一个节点的第一时间就标记它。迭代栈实现中标记时机错误如前所述迭代实现必须在节点入栈时标记而不是出栈时。否则同一个节点可能被多次压入栈中。递归深度限制Python默认递归深度约1000。处理深度可能很大的树或图时要么改用迭代栈要么使用sys.setrecursionlimit()提高限制需谨慎可能引发段错误。在回溯法中忘记“撤销选择”这是回溯法的精髓。path.append()和used[i]True是“做选择”递归调用后必须有对应的path.pop()和used[i]False来“撤销选择”恢复现场否则状态会混乱。混淆遍历顺序对于二叉树前序、中序、后序结果不同。对于图DFS的顺序不唯一取决于邻居的存储和访问顺序。在需要特定顺序时要小心控制。在需要记录路径时错误地传递引用在Python中列表是可变对象。当将路径path加入结果集res时如果直接res.append(path)加入的是对同一个path列表的引用。后续对path的回溯修改pop会影响已经存入res的结果。必须使用res.append(path[:])或res.append(list(path))进行拷贝。网格DFS中的方向数组写上下左右四个方向时务必检查坐标加减是否正确一个笔误就会导致搜索错误。建议统一定义一个方向数组dirs [(-1,0),(1,0),(0,-1),(0,1)]用循环处理避免重复代码和笔误。深度优先搜索这个看似简单的“一条路走到黑”的策略其内涵和应用远比表面看起来丰富。从最基本的图遍历到复杂的回溯、拓扑排序、记忆化搜索它构成了算法世界中一块坚实的基石。理解它的递归与栈的双重本质掌握其在不同数据结构上的模板并学会应用剪枝、记忆化等优化技巧你就能游刃有余地解决一大类搜索和枚举问题。下次再遇到“一笔画”或者“所有可能排列”这类问题时不妨先想想DFS能帮上忙吗