企业官网建设流程全解析

一说“搜索之 DFS”，很多人第一反应是刷题网站上的“深度优先搜索”，脑子里立刻浮现出递归、回溯、二叉树、全排列那套东西。但把搜索这个词往外稍微拉一拉，你会发现 DFS 其实是整个算法体系里最贴近“人本能”的一种搜索方式——人走进一个分岔路口，凭直觉往一条路走到头，走不通再退回来换一条，这不就是深度优先吗？所以这篇博文我不想只重复教科书里的定义，而是想从“为什么 DFS 靠谱”“怎么写才能不出错”“哪些场景真能派上用场”三个角度，把这条经典搜索路径彻底讲透。

适合看这篇内容的人，我大概分三类：一是刚开始刷算法题、对递归和搜索树还比较懵的初学者；二是工作中需要处理遍历、求解、排列类问题的开发者，想系统梳理一下 DFS 的完整写法和坑点；三是准备面试、希望用最短时间把 DFS 相关的常考题型抓牢的朋友。我下面讲的所有内容，都会围绕“搜索之 DFS”这个核心展开，把思路、代码、调试经验一次说清楚。

1. 搜索之 DFS：先弄懂它在搜什么

1.1 深度优先到底是什么

深度优先搜索（Depth-First Search，简称 DFS）的核心行为可以用一句话概括：从起点出发，沿着一条路径尽可能走到尽头，走不通就退回上一个岔路口，再换下一条路径继续尝试。

这句话里藏着两个关键动作，一个是“深入”，一个是“回溯”。深入指的是顺着某条分支一层层往下走，每走一步就把当前状态压入一个隐式的搜索栈；回溯则是当当前分支无法继续（要么到底了，要么不符合要求）时，撤销当前状态，回到上一层，尝试其他未被访问过的分支。

生活化的例子特别多。比如你在一栋陌生的办公楼里找一间会议室，进了走廊后先往左边走，左走到头发现是安全通道，退回来再走中间的走廊，中间走到一半看到分叉，先试左分叉，又到头了退回来走右分叉……这一整套行为，就是 DFS。如果反过来的话，你会先把每一层的所有房间都快速扫一遍，再往下一层去，那就是宽度优先搜索（BFS）的思路了。

既然是“搜索之 DFS”，搜索目标不只是“找到某个节点”，还可能是找路径、找可行解、找最优解前置的枚举集合。比如迷宫问题，目标是走到出口；排列问题，目标是生成所有排列；连通性问题，目标是找出所有连成一片的格子。DFS 在不同场景里只是“状态定义”不同，底层机制是完全一致的。

1.2 为什么 DFS 是搜索问题的第一选择

你可能会问：能搜索的算法那么多，为什么 DFS 地位这么高？

最直接的原因是实现简单、思路直观。一个递归函数加几个参数，就能完成一次完整的状态空间遍历。相比之下，BFS 需要维护队列、记录层数，代码量明显更大；而更高级的搜索优化，比如双向 BFS、启发式搜索（A*、IDA* 等），很多时候也是在 DFS/BFS 骨架上做文章。

其次，DFS 天然贴合“试探-回溯”的求解模式。很多问题并不是单纯找一条路，而是需要尝试所有可能性，再判断哪个方案合法。比如八皇后问题、数独求解、组合拆分，这类问题的本质是“在状态树上枚举”，DFS 是唯一一个用最少代码量就能完整覆盖整棵状态树的算法。

还有一点，DFS 的空间效率在深度优先进行时表现优异。树或图的搜索过程中，DFS 只需要存储当前路径上的节点，也就是栈的深度；而 BFS 需要存储一整层的节点。在最坏情况下如果搜索树很深但相对窄，DFS 的空间消耗会远小于 BFS。当然这不是绝对的，深到会让栈溢出时也要注意，这点我在后面章节专门讲。

所以在大多数“求所有解”或“判断是否存在解”的场景里，DFS 永远是第一个被想到的方案。它未必是最快的，但一定是最不容易写错、最方便调试的那个。

2. DFS 的核心机制与避坑清单

2.1 递归的本质：系统栈在背后做了什么

写 DFS 最常见的姿势就是递归。递归之所以能实现“深入再回溯”，依赖的是函数调用时系统自动维护的调用栈。

每次调用递归函数，系统会把当前函数的局部变量、参数、返回地址压入栈中；函数返回时，栈帧弹出，恢复到调用前的状态。从抽象层面看，这个栈帧就是“当前搜索路径上的状态”。递归的好处是，你不需要自己管理状态的回退，每次调用从函数返回，状态自然恢复到上一层的值。

看一个最简单的二叉树前序遍历：

def dfs_preorder(node): if node is None: return visit(node) # 访问当前节点 dfs_preorder(node.left) # 深入左子树 dfs_preorder(node.right) # 深入右子树

函数先访问当前节点，然后朝左子树一头扎进去，左子树全部走完再回到当前节点，继续右子树。这个“回到当前节点”的动作，靠的就是左子树调用结束后栈帧自动弹栈、变量值恢复。

但递归并不总是完美的。有两个隐患需要提。一是当搜索深度过大时，系统栈被撑爆，程序直接崩溃（Python 里最常见的报错是 RecursionError）。二是递归函数里如果对状态变量做了修改，忘记在返回前撤销（回溯），那么后续分支访问到的就是被污染的状态，结果出错。

2.2 递归爆炸风险与手写栈方案

系统栈的空间并不是无限的，默认情况下，Python 的递归深度限制通常是 1000 层左右。如果搜索空间本身相当深，比如在处理某些树形结构、迷宫网格时一探到底，递归版 DFS 会直接触发 RecursionError。

此时有两个处理方向。

第一个方向是调整递归深度限制：

import sys sys.setrecursionlimit(100000)

这个办法能让一部分场景继续跑下去，但治标不治本。如果深度特别大，还是会崩，而且过深递归在性能上也存在风险。

第二个方向是手写栈模拟递归，这是推荐掌握的技术。用显式的列表（栈）存储待访问的状态，替代函数调用栈。迷宫逃出问题的迭代版写法就是这样：

def dfs_maze_iterative(maze, start, target): stack = [start] visited = set() visited.add(start) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] while stack: x, y = stack.pop() if (x, y) == target: return True for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and (nx, ny) not in visited and maze[nx][ny] != '#': visited.add((nx, ny)) stack.append((nx, ny)) return False

这套写法不受递归深度限制，而且状态管理完全看得见摸得着。唯一要注意的是，迭代版的“访问顺序”和递归版存在细微差异，但搜索结果不受影响，因为目标是把状态空间走完。

2.3 剪枝：让搜索量急剧下降的要害

DFS 的朴素逻辑是所有分支全部遍历，复杂度通常是指数级。真正让 DFS 从“理论上能搜”变成“实际能用”的关键，就是剪枝。

所谓剪枝，就是在搜索过程中提前判断某条分支已无希望，直接跳过，不继续深入。剪枝的时机有三类：

• 合法性剪枝：当前状态已经违反约束条件，立即停止。
• 边界剪枝：网格搜索中越界的位置直接返回。
• 最优性剪枝：已经找到过一组解，而当前路径长度已经超过历史最优，就没必要继续走了。

最典型的一个例子是 N 皇后问题。每一层放一个皇后，但如果新放的位置会和之前的皇后互相攻击，就不用继续往下一层递归了，直接回溯。这个剪枝能把穷举所有摆法的巨大搜索量压缩到非常小的规模。

代码里体现剪枝的一般范式是这样：

def dfs_nqueens(row, n, cols, diag1, diag2, result): if row == n: result.append(cols[:]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # 剪枝 cols.append(col) diag1.add(row - col) diag2.add(row + col) dfs_nqueens(row + 1, n, cols, diag1, diag2, result) cols.pop() diag1.remove(row - col) diag2.remove(row + col)

剪枝的作用放在面试和实际工程里都是“能把一小时的超时变成毫秒级返回”的立竿见影手段。很多人觉得 DFS 慢，其实是没剪枝，或者剪枝条件放得太靠后。

3. 两种最常用的 DFS 写法与调试技巧

3.1 递归实现：以迷宫逃出为例

迷宫问题是搜索之 DFS 最容易理解的载体。这里说一个带状态标记的完整实现。假设迷宫用二维数组表示，0代表可走，1代表墙，起点是(0,0)，目标是(m-1, n-1)。

def dfs_maze_recursive(maze, x, y, target_x, target_y, visited): if not (0 <= x < len(maze) and 0 <= y < len(maze[0])): return False if maze[x][y] == 1 or (x, y) in visited: return False if x == target_x and y == target_y: return True visited.add((x, y)) for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: if dfs_maze_recursive(maze, x + dx, y + dy, target_x, target_y, visited): return True return False

这里有几个细节值得注意。第一，visited集合非常关键，它保证同一个格子不会被反复探索，否则在网格里会来回打转形成死循环。第二，边界检查要放在迷宫值检查之前，否则索引会越界报错。第三，返回的时机要谨慎：找到目标就应该立刻一层层返回 True，而不是继续搜索其他分支。

写递归 DFS 的时候，我建议把“当前层只管当前层的事”当成原则。这句话的意思是，当前这层递归只负责判断当前位置是否合法、是否到达目标、然后向四个方向发起调用，至于深层的结果如何处理，不属于当前调用的职责。一旦想混在一起，代码就很容易出错。

3.2 迭代实现：手写栈解决爆栈

迷宫逃出的迭代版本在前面已经给出过，这里重点讲一下递归和迭代在写法上的对应关系。

递归版的逻辑是：当前状态放在函数参数里，调用子任务时，子任务的状态通过参数传递；子任务结束返回，本层继续处理剩余方向。迭代版则是：把待处理状态放进栈里，每次弹出一个状态，处理它，再把新状态压入栈中。两者的区别在于，递归的栈帧由系统管理，迭代的栈由我们自己管理。

所以迭代版要额外维护的信息是“当前处理到哪个方向了”。如果只是简单地把下一个位置压栈，不需要记录方向，上面代码就能满足。但如果你要 DFS 输出一条完整路径，而不是单纯判断可达性，就需要把“路径上下文”一并压入栈。

def dfs_maze_path(maze, start, target): stack = [(start, [start])] # (当前位置, 已走路径) visited = {start} while stack: (x, y), path = stack.pop() if (x, y) == target: return path for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]: nx, ny = x + dx, y + dy if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and (nx, ny) not in visited and maze[nx][ny] != 1: visited.add((nx, ny)) stack.append(((nx, ny), path + [(nx, ny)])) return None

这里把路径随状态一起存储，虽然会占用一定内存，但在深度不大时比回溯维护的方式更容易理解。如果谜宫格子数量很大，更省内存的方案是每个状态记录“上一个状态”，最后再反向还原路径。这套做法在竞赛里很常见，面试中如果被追问，也是加分项。

3.3 边界条件与常见错误速查

DFS 不出错的关键，在于把边界条件和状态还原理顺。我把实际踩过的坑整理成了下面这个速查表，发布到社区以后反响一直不错：

这个表里的每一项，我几乎都在实际写题和工作里遇到过。尤其是“未回溯状态”和“忘记标记已访问”两个问题，占比最高。

4. 三个高频场景：全排列、连通块、搜索二叉树

4.1 全排列问题：DFS 与回溯的结合

全排列是 DFS 的经典入门题，也是面试出现频率极高的问题。求一个数组的所有排列，本质上就是遍历一棵排列树：第一位选哪个数字，第二位选哪个数字，以此类推。

def permute(nums): result = [] used = [False] * len(nums) def dfs(path): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) dfs(path) path.pop() used[i] = False dfs([]) return result

这段代码最核心的是path.pop()和used[i] = False这两行。没有这两行，前面选过的数字就永远留在状态里，后续分支都会被错误地“锁定”。很多新手第一次写全排列，结果莫名其妙缺少很多排列，基本就是回溯这一步漏了。

我在讲 DFS 回溯时喜欢用一个比喻：递归往下走是出门探索，回溯就是把出门带的东西原样放回原位，确保下一次出门时家里和出门前一样。

排列的去重也是容易出错的点。如果 nums 里含有重复数字，需要在排序后加一个条件：如果当前数字和前一个数字相同，且前一个数字没被用过，跳过。这个写法初看比较绕，实际记住一句话就行：重复数字只能从前往后依次使用。

4.2 连通块问题：网格型 DFS

连通块问题把 DFS 从“找路径”扩展到了“找区域”。典型场景包括岛屿数量、被围绕的区域、图像处理里的区域填充等。核心是在一个二维网格里，从某个点出发，把所有相连的同类格子全部标记一遍。

def num_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = [[False] * cols for _ in range(rows)] count = 0 def dfs(x, y): if not (0 <= x < rows and 0 <= y < cols): return if grid[x][y] == '0' or visited[x][y]: return visited[x][y] = True dfs(x + 1, y) dfs(x - 1, y) dfs(x, y + 1) dfs(x, y - 1) for i in range(rows): for j in range(cols): if grid[i][j] == '1' and not visited[i][j]: count += 1 dfs(i, j) return count

这段代码里有一个隐藏得很深的问题，让我在真正写这类题目时栽过跟头：递归调用四个方向的顺序不影响正确性，但极端情况下会影响 dfs 函数的栈深度。如果你总是先走上、再走右、再走下、再走左，在一条很长的竖向网格里，递归深度会被拉满；如果先走上下再走左右，类似情况也可能发生。所以当网格特别大时，为了稳定性，建议直接改成手写栈版本。

还有一个空间优化技巧：直接修改原始 grid 把访问过的陆地标记成'0'，可以省掉 visited 数组。但这种做法会改变输入数据，“允许修改入参吗”需要先确认。面试时可以提一句这个想法，再根据面试官反馈决定是否真的修改。

4.3 搜索二叉树查找：别把 BST 当成普通树

既然热词里有“搜索二叉树”，这里单独讲一下 BST（Binary Search Tree）里的 DFS。BST 是排序过的二叉树，左子树所有节点值都小于根，右子树所有节点值都大于根，所以理论上查找节点时利用这个有序性，平均复杂度只有 O(log n)。

但 DFS 的思维惯性让我们容易犯一个错误：把 BST 当成普通二叉树，所有节点一律进行三路遍历，完全不利用排序信息。这不会错的，只是用不上 BST 的优势。

正确做法是每一层根据目标值和当前节点值的大小关系，只深入一个子树。

def search_bst(root, val): if root is None or root.val == val: return root if val < root.val: return search_bst(root.left, val) return search_bst(root.right, val)

这里最关键的是，不需要同时递归左右两边。任何一次查找，路径上的每一步都只可能去一边。这意味着搜索路径的深度直接由树的平衡程度决定。

如果是极端的 BST（退化成链表），DFS 深度会变成 n，再套递归写法就会栈溢出。应对手段是写迭代版查找：

def search_bst_iterative(root, val): cur = root while cur is not None and cur.val != val: if val < cur.val: cur = cur.left else: cur = cur.right return cur

熟悉这个版本之后，相关的 BST 区间搜索、最近公共祖先、验证 BST，都能很快推出正确的 DFS 结构。

5. 常见问题与排查心得

5.1 只过样例不过大数据的排查思路

这是写 DFS 最容易遇到的一种情形：本地小数据测试全对，一到大数据或者在线评测就超时或答案错。

先看超时。超时的原因绝大多数是剪枝不充分或没有记忆化。DFS 在搜索树庞大的情况下会指数级膨胀，只靠“尽量剪枝”很难彻底解决，很多问题需要把中间结果缓存下来，也就是记忆化搜索。记忆化的本质是把已经计算过的状态存起来，下次直接查表。它能把很多指数级的搜索降成多项式级别。

再看答案错。大数据下答案错，一个典型原因是数据结构选得不对。比如判断“某个元素是否在当前路径中”用了列表，每次判断是 O(n)，小数据看不出问题，数据量上来就会超时；换成集合或布尔数组就没事。另一个原因是 hash 类容器引入了随机因素，某些语言里字典/哈希表遍历顺序不稳定，可能导致不同分支的搜索顺序不同，从而影响到“需要保留首次结果”的场景。

排查时我有个固定套路：先把递归深度上限临时调大，排除 RecursionError 对结果的干扰；然后用尽量小的数据，手动逐行推一遍递归树；最后在递归函数开头打印当前状态，观察有没有异常分支。打印法是调试腹膜，屡试不爽。

5.2 无限递归与栈溢出定位方法

无限递归是最让人头疼的 DFS 故障，因为程序不会立刻报错，而是会一直跑，直到资源耗尽才崩溃。

定位时先思考两个问题：状态是不是在重复？结束条件是不是永远没机会满足？

重复状态的发生，在写树的时候不常见，因为树天然没有环；但在图、网格、迷宫这类场景里极其常见。没有 visited 集合或者 visited 维护在错误位置，都会出现 A 到 B、B 又到 A 的死循环。

结束条件不满足，常见于深度目标设错。比如全排列里应该判断len(path) == len(nums)，但写成len(path) > len(nums)，那永远不会相等，递归会一直超出长度边界。这种错误在小测试里特别容易漏过去。

栈溢出的定位方式也很有意思：如果你用 Python 收到RecursionError: maximum recursion depth exceeded，在报错信息里通常能直接看到递归函数的调用链。Linux 用ulimit -s unlimited临时调大栈空间是一个办法，但根本上还是要改写迭代版本。

5.3 两个实用调优技巧

最后分享两个我实际用下来很有效的调优技巧。

第一个是DFS+BFS 混合思路。有些迷宫最短路径类问题，纯 DFS 穷举所有路径会非常慢，因为 DFS 天生不是求最短路的。这时候可以先用 DFS/二分先把“可达性”做出来，再用 BFS 去找最短路径。另一种常见混合是“双向搜索”：从起点和终点同时跑 DFS，两边各走一半深度再汇合，搜索量能指数级下降。

第二个是为 DFS 写一层函数缓存层。这个思路也常叫记忆化或备忘录。判断是某一个状态是否已经计算过，如果计算过直接返回结果。比如字符串切分问题，就把“当前起点位置”作为 key，把“从当前位置能否成功切分”存起来。由于 DFS 的调用栈天然适合缓存，代码上的改动往往只有几行，但运行时间可能从数秒降到毫秒。

我倒不觉得 DFS 需要背太多模板，更重要的是一旦理解了“深入+回溯”这套底层机制，所有变种都能自然地推导出来。实际写代码时，用递归还是手写栈，走迷宫还是摆皇后，区别只在于状态的定义和剪枝的精准度。把这两个点想明白，搜索之 DFS 在绝大多数场景下都能又快又稳地完成任务。