企业官网建设流程全解析

DFS（深度优先搜索，Depth-First Search）是我在算法工作中用得最多、也最容易被低估的一个基础算法。很多人把它理解为“递归遍历”，刷题时套模板，遇到复杂一点的题目就卡壳。但实际上，DFS是一种遍历状态空间的基本策略，排列组合、图连通性、拓扑排序、迷宫寻路、表达式解析这些场景，底层都是同一套思路。这篇文章我想从一个程序员的实际角度出发，讲清楚DFS到底在做什么、怎么写不会出错、怎么剪枝提速、碰上栈溢出怎么办，让刚入门的人能直接上手，让已经刷过不少题的人也能补上一些盲区。

1. 先搞清楚DFS到底在做什么

1.1 用一个生活场景理解深搜

想象你在一个陌生的商场里找出口，手上没有地图。最笨但一定走得通的方法是：随便选一个方向一直往前走，遇到岔路就选一条继续走，走到死路就退回到上一个岔路，换一条没走过的方向再走。这样反复折腾，最后能把整个商场的所有通道都过一遍。这个过程就是“深度优先”——先尽可能往深处走，走不通再回头。

我把这个画面记了很多年，因为它准确抓住了DFS的两个关键词：“深入”和“回溯”。深入是说每次只沿着一条路径走到黑；回溯是说走不通时沿着原路退回最近的分叉点。对应到程序里，“深入”靠递归或栈的不断压入实现，“回溯”靠函数返回或栈弹出实现，而“没走过的方向”则用一个状态标记来记录。

1.2 DFS的本质：状态空间的遍历

绕开树和图的表象，DFS真正处理的是“状态空间”。所谓状态，就是搜索过程中某个时刻的完整信息快照，它可能是一个网格坐标、一个数字组合、一个棋盘布局，也可以是一个字符串的前缀。从初始状态出发，每做一次选择就进入一个新状态，所有可能的路径构成一棵“决策树”或者一张“状态图”。DFS就是在这棵树上做深度优先的遍历。

这里有两点特别重要。第一，DFS不做任何启发式判断，不看哪个方向更接近答案，它只是机械地穷举，所以正确性容易保证，代价是可能很慢。第二，DFS遍历的顺序是“一条路走完再换路”，所以它天然适合需要“枚举所有可能”的问题，比如所有排列、所有子集、所有可行路径。很多人觉得DFS难，是因为把注意力放在递归调用上，其实核心是状态定义和转移规则：状态是什么，从当前状态可以转移到哪些状态，什么条件下终止。

2. 两种实现方式：递归与显式栈

2.1 递归写法：最贴近直觉的深搜模板

递归是描述DFS最自然的方式，因为“深入下一个状态”就是函数自己调用自己，“回溯”就是函数返回。我常用的模板长这样：

def dfs(state, ...): # 1. 递归出口：判断是否到达目标状态 if is_goal(state): process(state) # 记录答案或做统计 return # 2. 枚举当前状态的所有下一步选择 for choice in get_choices(state): next_state = apply(state, choice) # 3. 合法性检查 / 剪枝 if not is_valid(next_state): continue # 4. 标记状态（防止同一个状态被重复搜索） mark(next_state) # 5. 递归深入 dfs(next_state, ...) # 6. 撤销状态（回溯，让兄弟分支也能使用该状态） unmark(next_state)

这个模板里的每一步都有明确职责。第1步是“递归出口”，没有它就会无限递归；第2步是“状态转移”，决定你能探索多少分支；第4步和第6步合起来是“标记与撤销”，处理搜索过程中状态重叠的问题，少了撤销，兄弟分支之间会互相污染。我把这六步称为“DFS六件套”，写任何深搜都按这个顺序捋一遍，基本不会漏。

拿一个最经典的例子——求一个数组的所有不重复排列——来演示：

def permute(nums): result = [] path = [] used = [False] * len(nums) def dfs(): if len(path) == len(nums): result.append(path[:]) # 注意拷贝 return for i, num in enumerate(nums): if used[i]: continue used[i] = True path.append(num) dfs() path.pop() # 撤销选择 used[i] = False # 撤销标记 dfs() return result

这段代码初学者最容易犯两个错误：一是往结果里塞path而不是path[:]，导致后面pop时已经存进的答案全被改掉；二是在 for 循环里漏掉used[i] = False，导致只输出一条路径就结束。我建议至少亲手手写三遍这个全排列，把压栈、回退、拷贝这三个动作在脑子里过清楚。

2.2 显式栈写法：什么时候选择它

递归虽然直观，但也有两个硬伤：一是递归深度受调用栈限制，Python 默认递归上限大约 1000 层，深度较大的图一次深搜就能触发RecursionError；二是递归调用有额外开销，状态特别多时性能不如显式栈稳定。这时候就该换显式栈。

def dfs_stack(start): stack = [start] visited = set([start]) while stack: node = stack.pop() process(node) # 处理当前节点 for nxt in neighbors(node): if nxt not in visited: visited.add(nxt) stack.append(nxt)

注意这里的visited是在入栈时就标记，而不是在弹出时标记。如果等到弹出才标记，同一个节点可能被压入多次，在大图上会浪费大量内存和时间。显式栈写法的好处是深度不受调用栈限制，逻辑流程完全掌控在自己手里，难处是要手动维护“下一个待访问节点”的顺序——栈是后进先出，所以后加入的邻居会先被访问，这与递归版本的分支顺序正好相反，排查时容易踩坑。

实际工程中我两条路线都用：小规模问题、代码可读性优先时用递归；依赖复杂、深度可能超过千级、或需要动态控制搜索顺序时用显式栈。千万不要迷信递归是“唯一正统”，两个版本都要能随手写出来。

3. 经典场景拆解：从全排列到图遍历

3.1 排列、组合与子集：模板的直接套用

排列、组合、子集是DFS最典型的三个入门场景，本质上都是“从若干个元素里按规则选出一批”。排列关心顺序，组合不关心顺序，子集则是所有可能的选择结果。它们的递归模板几乎一模一样，区别只在于下一层搜索的起始位置。

# 组合：从 n 个元素中选 k 个，不关心顺序 def combine(n, k): result = [] path = [] def dfs(start): if len(path) == k: result.append(path[:]) return for i in range(start, n + 1): path.append(i) dfs(i + 1) # 关键：下一层从 i+1 开始，保证不重复 path.pop() dfs(1) return result

排列和组合的区别就在dfs(i + 1)这句。排列每次都能用之前用过的元素，所以需要used数组做全局标记；组合要求“后面的选择不从前面选”，所以直接把搜索起点往后推，天然去重。这个“起点后移”的技巧还能延伸出很多变体，比如元素有重复时需要先排序，再跳过相邻重复项，避免产生相同的组合结果。

子集问题其实可以看作“选或不选”的二叉树递归。每个元素只有两个分支：加入当前集合，或者不加入。走到叶子就产生一个子集。这类问题在真题里出现频率极高，可以把上一段的组合模板记熟，子集就是k从 0 到n的所有组合拼在一起。

3.2 图与树的遍历：连通性、岛屿与拓扑排序

DFS在图论里最直接的应用是连通性判断。比如一张二维网格上的“岛屿问题”，求有多少块连通的陆地，代码就是把每个未访问的陆地作为起点做DFS，一次DFS能覆盖一整块岛屿：

def num_islands(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x, y): if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '0': return grid[x][y] = '0' # 直接改成水，省掉 visited 数组 for dx, dy in directions: dfs(x + dx, y + dy) count = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 dfs(i, j) return count

这里有个小技巧：访问过的陆地直接原地标记为'0'，省掉一个visited二维数组。面试场合很加分，实际代码也更干净。不过要注意，这种做法会修改原始数据，如果后续还要用原始网格，记得先拷贝。树的遍历同样可以用DFS，前序、中序、后序本质上就是“先访问节点”和“先深入子树”的不同排列。

拓扑排序也是DFS的经典应用。对有向无环图做DFS，按节点的完成时间从晚到早排列，就得到拓扑序。我在实际工作中用拓扑排序解析过依赖配置文件，处理“A依赖B，B依赖C”的先后关系，DFS版本比队列版本的代码更好讲清楚循环依赖怎么检测——只要DFS过程中遇到一条回到祖先节点的边，就说明存在环。

3.3 回溯法：状态撤销的完整演练

回溯法是DFS最精华的变体，核心思想是“做选择、深入、撤销选择”。典型代表是N皇后问题和迷宫寻路。以迷宫为例，每走一步就压入一个方向，走到死路就退回上一步换方向，直到找到出口。

def solve_maze(grid, sx, sy, ex, ey): m, n = len(grid), len(grid[0]) path = [] directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] def dfs(x, y): if (x, y) == (ex, ey): path.append((x, y)) return True path.append((x, y)) grid[x][y] = 2 # 标记为已访问 for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0: if dfs(nx, ny): return True path.pop() # 此路不通，撤销当前位置 grid[x][y] = 0 # 恢复原状 return False if dfs(sx, sy): return path return None

回溯的难点在于一定要把“标记”和“撤销”看成一对绑定操作。标记是为了不让当前路径重复绕圈，撤销是为了让其他路径能够经过这个点。新手最常见的问题是只标记不撤销，结果漏掉大量可行路径；或者撤销时机放错，导致当前路径还没走完就被其他分支“借用”了状态。写回溯的时候我会在注释里明确标出哪一行是“进入分支前的标记”，哪一行是“离开分支后的清理”，这样代码一长也不会乱。

4. 剪枝与优化：DFS能不能快一点

4.1 三类剪枝：可行性、最优性与重复状态

DFS最大的软肋是穷举导致状态爆炸。比如 20 层的完全二叉树就有 100 多万个叶子节点，硬搜肯定不行。剪枝是DFS性能优化的核心手段，我把它分成三类。

第一类是可行性剪枝。在深入之前就判断这个分支是否还“有可能”到达目标，不可能就直接跳过。比如走迷宫时，当前点离出口的曼哈顿距离已经大于剩余步数，那这条分支再走也是白费，直接剪掉。第二类是最优性剪枝，主要用于求最短/最小解的题：如果当前路径的代价已经大于等于目前已知的最优解，那就没必要继续搜了，因为后续只会更差。第三类是重复状态剪枝，也就是用visited、used或记忆化数组记录哪些状态已经搜索过，避免同一个状态被反复计算。

三类剪枝不是互斥的，实际题目里经常叠加使用。我的建议是先把重复状态剪枝做成习惯，因为它是正确性的一部分，漏了可能会超时甚至死循环；可行性剪枝和最优化剪枝需要根据题目条件灵活设计，属于进阶优化，放在第二优先级。

4.2 搜索顺序：同样的DFS，快慢可以差十倍

剪枝之外，搜索顺序是另一个很容易被忽略的性能变量。对于同一组分支，如果先走“更容易到达目标”的分支，那么最优性剪枝就能更早生效。举个具体例子，凑零钱问题中如果把候选硬币面额从大到小排序，DFS会先尝试大额硬币，路径深度更快逼近目标金额，剪枝效果比从小到大排序好很多。

类似地，迷宫问题里按“接近出口的方向优先”的顺序探索邻居，往往能在几步之内就找到一条可行路径，而一个反方向的搜索可能要回溯几百次。搜索顺序不影响DFS的正确性，只影响发现答案的速度，所以在动手之前先琢磨一下“哪个分支最可能成功”是值得的。这里有一个经验：搜索顺序的设计依赖具体约束条件，最有效的是分析约束最强的变量——比如数独题里优先填可选数字最少的格子，这叫最大约束优先原则。

4.3 记忆化：DFS加上缓存就变成了动态规划

有些DFS会反复搜索同一个状态。典型的例子是斐波那契数列的朴素递归，fib(5)会算两遍fib(3)，指数级膨胀。解决办法是给DFS加一个缓存：每个状态第一次算完就存起来，下次再遇到直接取结果。这就是记忆化搜索，也可以理解为自顶向下的动态规划。

from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)

记忆化和剪枝的区别在于：剪枝是主动放弃一些分支，记忆化是把已经算过分支的结果缓存复用。两者常常配合使用。什么时候该想到记忆化？一个简单的判断标准是：DFS函数里如果只依赖少数几个参数决定后续状态，而且这些参数的不同取值组合明显少于搜索树的分支数，那大概率存在大量重复状态，上记忆化会有效。另一个判断方法是自己画一遍小规模的状态树，看到同一个节点出现多次就说明该缓存了。

5. 实操中常见的问题与排查方法

5.1 无限递归与栈溢出

这是DFS最经典的事故现场。症状是程序卡死、RecursionError或直接段错误。原因通常有两个：一是递归出口条件写错，永远到达不了终止状态；二是图中有环，而visited标记写得不对，导致节点被反复访问。排查时我会先在一张很小的图上手动模拟两三步，看递归参数有没有收敛趋势。如果是递归深度超出Python默认限制，可以在明确知道深度上限小于系统栈容量的前提下临时调大sys.setrecursionlimit，但更稳妥的做法是改成显式栈。在工程系统里处理几万层嵌套的目录结构时，我踩过递归溢出的坑，那次之后凡是深度不确定的遍历，我都默认写显式栈。

5.2 忘记撤销状态导致答案缺失

回溯问题里，状态需要“用完就还”。漏掉撤销的典型表现是：输出的结果数量偏少、或者某些路径被错误地否决。这很难定位，因为程序不报错，只是答案不对。我的排查方法是给DFS加上一个全局计数器，对比预期结果数量，再逐层打印状态变化。如果发现某一层进入分支时状态已经被上一层改过，就说明撤销逻辑有问题。建议把“标记与撤销”封装成两个成对的小函数，比如enter_state()和leave_state()，从结构上减少遗漏。

5.3 visited与路径标记混用

很多新手把visited（全局访问标记）和回溯里的临时标记混在一起。它们语义不同：visited表示“整个搜索过程中这个状态已经处理过，永远不会再进来”，而回溯的临时标记表示“当前这条路径经过了这个点，兄弟路径需要用的时候可以重新进入”。如果混用，要么漏答案，要么死循环。一个简单的区分标准是：题目要求求“所有路径”时用临时标记加撤销；求“是否存在可达性/连通分量/遍历全部节点”时用全局visited。遇到分不清的题目，先问自己一句：这个状态去掉之后，另一条分支还敢不敢再来？敢，就用临时标记。

5.4 常见问题速查表

这张表是我平时排错的快速索引。遇到问题我习惯先对着表把“是不是某个常见根因”过一遍，比从头读代码快得多。还有一个隐藏问题：如果DFS里使用了全局变量记录答案，多组测试数据之间记得重置这些全局状态，否则上一组的答案会污染下一组。

6. DFS 与 BFS 怎么选

6.1 两者的本质区别

BFS（广度优先搜索）和DFS一样都是遍历状态空间的基本方法，区别只在访问顺序。DFS用栈（或递归）维护待处理节点，先把一条分支走到底；BFS用队列维护待处理节点，按层推进。这个顺序差异带来一个关键性质：在无权图中，BFS第一次到达目标节点的路径一定是最短路径，而DFS第一次到达目标节点的路径通常不是最短路径。

所以选择的第一原则是看需求。求“是否有解”“有多少解”“枚举所有路径”，首选DFS；求“最短步数”“最少操作次数”“一层一层扩展的最优解”，优先BFS。另一个考量是空间复杂度：DFS在最坏情况下栈里存的是当前路径长度，而BFS队列里存的是整层节点，对于分支多的树，BFS内存消耗会明显更大。

6.2 一张表帮你做决定

这里补充一个我踩过的坑：曾经遇到一个社交关系链最短路径问题，写法上套了DFS，结果在近千万节点的图上运行极慢，因为DFS必须先走完海量分支才能发现最短路径。后来换成BFS，几秒就出结果。最短路径类问题，只要没有特殊限制，第一反应就应该是BFS，不要图省事套DFS模板。

6.3 两种思路可以相互借鉴

DFS和BFS不是对立的，很多高级算法是它们的融合。比如迭代加深搜索（IDDFS）就是反复用DFS限制深度，逐层加深，既保留DFS的空间优势，又能像BFS一样保证最短路径。A*算法可以理解成带启发式的BFS，而双向BFS则是从起点和终点同时做BFS，在中间碰头。

我的建议是先吃透DFS，因为它对“状态转移、回溯、剪枝”的锻炼非常充分，理解以后再学BFS会顺畅很多。反过来，如果先学BFS，遇到回溯类的题目容易想成“一步步扩散”，反而绕弯。两条路线都熟练掌握之后，看题目时那种“该用哪个”的感觉自然就有了。

7. 一些没写在教科书里的经验

最后分享几点我在实际项目中反复验证过的体会。第一，写DFS之前一定先画出状态树，哪怕只是在草稿纸上画两层，都能帮你理清状态参数应该传什么、出口条件怎么写。很多“看起来复杂”的题目，画完状态树之后发现就是模板的变体。

第二，递归深度是工程上线时最容易爆的雷。我在一个数据同步工具里用递归遍历多级目录，测试数据只有几十层没问题，上线后遇到深层嵌套目录直接栈溢出。后来统一改成显式栈，再也没出过问题。凡是输入规模不可控的场景，我默认不依赖递归。

第三，代码里的状态标记和撤销要写成相邻的两行，中间只隔递归调用。不要中间穿插好几层日志或额外计算，否则一加上调试逻辑就容易错位。我在给递归函数加打印日志时踩过这个坑，加着加着把撤销语句写到了continue后面，整个回溯逻辑直接失效。

DFS这个算法看起来简单，真正用好需要对状态定义、搜索顺序、剪枝条件和工程限制都有敏锐的感知。把这些经验消化掉，再遇到任何需要穷举和回溯的题目，你就能做到心中有数，而不是背模板碰运气。