4. 深度优先搜索（DFS）：算法原理、栈实现、递归与迭代两种方式
4.1 什么是深度优先搜索？
深度优先搜索，简称 DFS。说白了，就是一种「一条路走到黑」的搜索策略。
你想想看，在一个迷宫里找出口。你会怎么做？
大多数人会选一个方向，一直往前走。遇到岔路口，先选一条，继续走。直到撞墙了，或者发现这条路不对，才退回来换一条路。
这就是 DFS 的核心思想。
我个人习惯把 DFS 理解为「不撞南墙不回头」。它优先探索当前路径的深度，而不是广度。这和 BFS（广度优先搜索）正好相反——BFS 是先把当前层所有节点都看一遍，再往下走。
核心要点：DFS 沿着一条路径尽可能深地搜索，直到无法继续，然后回溯到上一个分叉点，选择另一条路径继续。
4.2 算法原理：递归与栈
DFS 的实现方式有两种：递归和迭代（显式栈）。
嗯，这里要注意。这两种方式本质上是等价的。递归调用时，系统会隐式地维护一个调用栈。而迭代方式，是我们自己手动维护一个栈。
我在项目中遇到过一个问题：递归实现虽然代码简洁，但深度太大时容易栈溢出。那时候处理一个 1000x1000 的网格地图，递归直接崩了。后来改成迭代栈实现，问题就解决了。
所以，两种方式你都得掌握。面试爱考递归，工程实战更推荐迭代。
4.2.1 递归实现
递归实现最直观。代码量少，逻辑清晰。
def dfs_recursive(graph, node, visited):
# 标记当前节点已访问
visited.add(node)
print(f"访问节点: {node}")
# 遍历所有邻居
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)你看，就这么几行。但有个坑——递归深度。Python 默认递归深度是 1000。超过就报 RecursionError。
避坑指南：我曾经在项目中用递归 DFS 处理一个深度 2000+ 的树结构，程序直接崩溃。后来用 sys.setrecursionlimit(10000) 临时解决，但最终还是改成了迭代实现。建议深度超过 500 就考虑迭代。
4.2.2 迭代实现（显式栈）
迭代实现需要我们手动维护一个栈。说白了，就是把系统帮我们做的事情，自己来做。
def dfs_iterative(graph, start):
visited = set()
stack = [start] # 用列表模拟栈
while stack:
node = stack.pop() # 弹出栈顶元素
if node not in visited:
visited.add(node)
print(f"访问节点: {node}")
# 将未访问的邻居入栈
# 注意：为了和递归顺序一致，这里逆序入栈
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)这里有个细节：为什么要逆序入栈？
因为栈是后进先出的。如果我们按顺序把邻居压入栈，那么最后一个邻居会先被访问。逆序入栈可以保证访问顺序和递归版本一致。
当然，如果你不关心顺序，直接正序入栈也行。
4.3 知识体系与核心逻辑
下面这张图，是我自己总结的 DFS 知识框架。你看一眼，心里就有谱了。
4.4 完整示例：网格地图路径搜索
光说不练假把式。咱们来一个实际例子。
假设有一个 5x5 的网格，0 表示空地，1 表示障碍物。我们从左上角 (0,0) 出发，要找到一条到右下角 (4,4) 的路径。
# 网格地图：0=空地，1=障碍物
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0]
]
def dfs_grid(grid, start, end):
rows, cols = len(grid), len(grid[0])
visited = [[False] * cols for _ in range(rows)]
path = []
# 四个方向：上、下、左、右
directions = [(-1,0), (1,0), (0,-1), (0,1)]
def dfs(r, c):
# 越界检查
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
# 障碍物或已访问
if grid[r][c] == 1 or visited[r][c]:
return False
visited[r][c] = True
path.append((r, c))
# 到达终点
if (r, c) == end:
return True
# 探索四个方向
for dr, dc in directions:
if dfs(r + dr, c + dc):
return True
# 回溯：此路不通
path.pop()
return False
if dfs(start[0], start[1]):
print(f"找到路径: {path}")
else:
print("无路径可达")
# 测试
dfs_grid(grid, (0,0), (4,4))个人经验：我在实际项目中做机器人路径规划时，DFS 通常用于「是否存在路径」的判断，而不是「最短路径」。因为 DFS 找到的第一条路径往往不是最优的。如果你需要最短路径，请用 BFS 或 Dijkstra。
4.5 递归 vs 迭代：怎么选？
| 对比维度 | 递归实现 | 迭代实现（显式栈） |
|---|---|---|
| 代码简洁度 | ⭐⭐⭐⭐⭐ 非常简洁 | ⭐⭐⭐ 一般 |
| 可读性 | ⭐⭐⭐⭐ 高 | ⭐⭐⭐ 中等 |
| 深度限制 | 受系统栈限制（约1000层） | 仅受内存限制 |
| 调试难度 | 较难（栈溢出不好定位） | 较易（可打印栈内容） |
| 性能 | 函数调用有额外开销 | 略快（无函数调用开销） |
| 推荐场景 | 深度可控的小规模搜索 | 深度未知或大规模搜索 |
4.6 避坑指南
做 DFS 这么多年，我踩过不少坑。分享几个最常见的：
- 忘记标记已访问节点——这会导致死循环。程序一直在两个节点之间来回跳，永远停不下来。
- 递归深度过大——我刚才说了，Python 默认 1000 层。处理大图时一定要小心。
- 栈的入栈顺序搞错——迭代实现时，入栈顺序决定了搜索顺序。如果你需要特定的访问顺序，记得逆序入栈。
- 回溯时忘记恢复状态——如果你在搜索过程中修改了全局状态（比如路径列表），回溯时一定要恢复。否则路径会越攒越多。
我曾经踩过的坑：有一次做八皇后问题的 DFS 实现，忘记在回溯时恢复棋盘状态。结果搜索到第 5 行时，棋盘已经被改得面目全非。排查了整整两个小时才发现问题。从那以后，我写 DFS 都会先检查「回溯恢复」这一步。
4.7 小结
DFS 是路径规划中最基础的算法之一。它的核心就是「栈 + 回溯」。
递归实现适合快速原型开发，迭代实现适合工程落地。我个人建议：面试时用递归展示思路，写代码时用迭代保证稳定性。
下一节我们会讲 BFS。到时候你会发现，DFS 和 BFS 就像一对双胞胎——长得像，但性格完全不同。
公众号:蓝海资料掘金营，微信deep3321