005 深度优先搜索（DFS）算法详解：图解+代码+经典例题

📌 什么是深度优先搜索？

深度优先搜索（Depth-First Search，DFS）是算法竞赛和面试中最高频的暴力搜索算法之一。其核心思想是“一条路走到黑”，从起点出发，优先探索最深的节点，直到无路可走再回溯，属于回溯算法的基石。

---

🌳 DFS算法思想

1. 核心流程（二叉树举例）

         A/   \B     C/ \   /D  E  FDFS遍历顺序：A → B → D → E → C → F

• 递归本质：系统调用栈实现“先进后出”
• 回溯条件：遇到叶子节点或访问完所有子节点后回退

2. DFS与BFS对比

特性	DFS	BFS
数据结构	栈（递归/显式栈）	队列
空间复杂度	O(h)（h为树高度）	O(w)（w为树宽度）
适用场景	路径问题、连通块	最短路径、层级遍历

---

🛠️ DFS实现方式

1. 递归模板（最常用）

def dfs(node, visited):if node in visited:  # 终止条件returnvisited.add(node)    # 标记已访问# 处理当前节点逻辑for neighbor in node.neighbors:  # 遍历子节点dfs(neighbor, visited)

2. 显式栈模板（避免递归溢出）

def dfs_stack(start):stack = [start]visited = set()while stack:node = stack.pop()if node not in visited:visited.add(node)# 处理当前节点for neighbor in reversed(node.neighbors):  # 保证顺序stack.append(neighbor)

---

🔥 DFS六大经典应用场景

1. 路径查找问题

• 例题：113. 路径总和 II
• 代码片段：

def pathSum(root, target):res = []def dfs(node, path, sum_val):if not node: returnsum_val += node.valpath.append(node.val)if not node.left and not node.right and sum_val == target:res.append(path.copy())dfs(node.left, path, sum_val)dfs(node.right, path, sum_val)path.pop()  # 关键回溯dfs(root, [], 0)return res

2. 连通块计数

• 例题：200. 岛屿数量
• 技巧：沉岛法（访问过的陆地标记为’0’）

3. 排列组合问题

• 例题：46. 全排列
• 关键：维护used数组记录已选元素

4. 拓扑排序

• 例题：207. 课程表
• 重点：检测图中是否存在环

5. 棋盘类问题

• 例题：51. N 皇后
• 优化：对角线剪枝（row-col和row+col标识）

6. 记忆化DFS

• 例题：329. 矩阵中的最长递增路径
• 核心：用memo数组避免重复计算

---

⚠️ DFS高频易错点

1. 忘记回溯

   path.append(node.val)  # 前进
   dfs(...)
   path.pop()            # 必须回溯！
   

2. 未剪枝导致超时
   通过排序+条件判断跳过无效分支（例：40. 组合总和 II）

3. 递归终止条件错误
   需明确递归到叶子节点或越界时的处理方式

4. 修改全局变量未恢复
   在修改全局状态（如矩阵元素）后，必须在回溯时还原

---

🚀 DFS优化技巧

1. 剪枝策略

• 可行性剪枝：提前排除不可能的解
  （例：17. 电话号码的字母组合中跳过空输入）

• 最优性剪枝：当前路径已劣于已知最优解时终止
  （例：剑指 Offer 34. 二叉树中和为某一值的路径）

2. 方向向量简化代码

# 四方向遍历
directions = [(-1,0), (1,0), (0,-1), (0,1)]
for dx, dy in directions:x_new, y_new = x + dx, y + dy

3. 双向DFS

• 适用场景：目标明确的搜索问题（如127. 单词接龙）
• 优势：将时间复杂度从O(b^d)降为O(b(d/2))，b为分支因子，d为深度

---

💡 学习建议

1. 先理解再背模板：通过二叉树遍历掌握递归流程
2. 从二维矩阵入手：岛屿类问题适合培养空间思维
3. Debug技巧：
   • 打印递归树层级
   • 使用可视化工具（如Python Tutor）
4. 延伸学习：
   • 回溯算法（DFS+剪枝）
   • 迭代加深搜索（IDDFS）
   • A*算法（启发式搜索）

---

📚 精选LeetCode练习题

题目	难度	核心考点
79. 单词搜索	中等	二维矩阵回溯
494. 目标和	中等	组合问题变形
473. 火柴拼正方形	中等	剪枝优化
980. 不同路径 III	困难	状态压缩

---

掌握DFS的关键在于大量练习和总结回溯模式。建议每天刷2-3题，坚持两周即可显著提升对DFS的掌控力！