4. 深度优先搜索(DFS)：一条道走到黑
深度优先搜索，简称DFS。这个名字很直白——就是往深处走，优先探索一条路径的尽头。
我个人习惯把DFS比作「走迷宫时贴着右边墙走」。你一直往右拐，直到撞墙，然后退回来换个方向。说白了，这是一种非常执着的搜索策略。
4.1 DFS算法原理
DFS的核心思想其实就八个字：不撞南墙不回头。
它的工作流程是这样的：
- 从起点出发，选择一个方向走
- 走到下一个格子后，继续选一个方向走
- 如果遇到死路（无路可走或已访问过），就原路退回
- 退回后换另一个方向继续尝试
- 直到找到终点，或者所有路径都试完
你想想看，这和BFS最大的区别在哪？BFS是「广撒网」，DFS是「深挖洞」。BFS一层一层推进，DFS一条路走到黑。
关键点：DFS使用栈（Stack）来管理待探索的节点。你可以显式地用代码实现一个栈，也可以利用函数调用栈——也就是递归。
嗯，这里要注意：递归写法虽然简洁，但地图大了容易栈溢出。我在项目中吃过这个亏，后面会细说。
4.2 DFS在栅格地图中的实现
先看代码，我直接给一个完整的实现。这个版本我用的是显式栈，不是递归。
def dfs(grid, start, goal):
"""
栅格地图上的深度优先搜索
grid: 二维数组，0表示可通行，1表示障碍物
start: 起点坐标 (x, y)
goal: 终点坐标 (x, y)
"""
rows, cols = len(grid), len(grid[0])
# 方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 用栈存储待探索的节点
stack = [(start, [start])]
# 记录已访问节点
visited = set()
visited.add(start)
while stack:
(current, path) = stack.pop()
if current == goal:
return path
x, y = current
# 遍历四个方向
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 检查边界和障碍物
if 0 <= nx < rows and 0 <= ny < cols:
if grid[nx][ny] == 0 and (nx, ny) not in visited:
visited.add((nx, ny))
stack.append(((nx, ny), path + [(nx, ny)]))
return None # 没找到路径个人经验：我刚开始写DFS时，总忘记把节点标记为已访问。结果就是死循环，程序卡死。后来我养成了一个习惯——入栈时就标记，而不是出栈时标记。这样可以避免重复入栈。
这段代码有几个地方值得注意：
- stack.pop()：从栈顶取节点，这就是「后进先出」
- visited.add()：入栈时立即标记，防止重复
- path + [(nx, ny)]：记录完整路径，方便返回
4.3 DFS与BFS对比
很多初学者会问：DFS和BFS到底选哪个？
我直接给结论：
| 对比项 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（Stack） | 队列（Queue） |
| 路径特点 | 找到的路径不一定最短 | 找到的路径一定最短 |
| 内存占用 | 取决于搜索深度 | 取决于搜索宽度 |
| 适用场景 | 解空间大、深度浅 | 解空间小、需要最短路径 |
为什么会这样？因为DFS的「后进先出」特性，导致它总是优先探索最新加入的路径。而BFS的「先进先出」特性，保证它一层一层推进。
我记得有一次做机器人路径规划，地图特别大，有1000x1000个格子。用BFS直接内存爆了，换成DFS反而跑出来了。虽然路径不是最短，但至少能用。
避坑指南：我曾经在一个项目中用DFS做路径规划，结果发现它找到的路径绕了很大一圈。后来我加了一个「深度限制」，超过一定步数就放弃当前路径。这样既保证了搜索效率，又不会太离谱。
4.4 DFS实战案例
来看一个具体的例子。假设我们有这样一个5x5的栅格地图：
地图布局（0=空地，1=障碍物）：
S 0 0 1 0
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0
1 1 0 0 G
S = 起点 (0,0)
G = 终点 (4,4)用我们的DFS代码跑一下：
grid = [
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
path = dfs(grid, start, goal)
print("找到的路径:", path)输出结果：
找到的路径: [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (2,2), (2,3), (2,4), (3,4), (4,4)]你仔细看这条路径。它先往下走到底，然后右拐，再往上绕了一下。这就是DFS的特点——它不会考虑「这条路是不是最短」，它只关心「能不能走到终点」。
如果换成BFS，找到的路径会是：
BFS路径: [(0,0), (0,1), (0,2), (1,2), (2,2), (2,3), (2,4), (3,4), (4,4)]明显短了一截。但BFS需要更多的内存来维护队列。
实战建议：
- 如果你需要最短路径，用BFS
- 如果地图很大，内存有限，用DFS
- 如果路径长度不重要，只要能到就行，DFS更省资源
- 如果地图中有大量死胡同，DFS可能会浪费很多时间在错误路径上
嗯，最后说一句。DFS虽然简单，但它是很多高级算法的基础。比如迭代加深搜索（IDA*）、回溯算法，本质上都是DFS的变种。把DFS吃透了，后面学A*算法会轻松很多。
下一章我们讲Dijkstra算法，它解决了BFS不能处理权重的问题。到时候你会看到，这些基础算法是怎么一步步进化成高级算法的。