DFS 算法

一、DFS 总纲

1.1 DFS 四大分类（90% 题目归属）

大类	搜索对象	本质
① 连通块 DFS	网格 / 图	染色 / 吞并
② 路径 DFS	树 / 图	枚举所有路径
③ 回溯 DFS	组合 / 排列 / 子集	枚举 + 剪枝
④ 边界 DFS	网格	先排除非法边界

二、① 连通块 DFS

2.1 适用场景

• 二维网格类题目
• 岛屿、区域、面积相关问题
• 核心特征：“相连的元素算一块”，只关心「连不连」，不关心具体路径

2.2 统一模板

function dfs(x, y) {
  // 1. 越界或状态不合法，直接返回
  if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== 合法值) {
    return;
  }

  // 2. 标记已访问，避免重复遍历
  grid[x][y] = 已访问标记; // 如：0 标记为 2，'1' 标记为 '0'

  // 3. 上下左右四向递归（网格通用）
  dfs(x + 1, y); // 下
  dfs(x - 1, y); // 上
  dfs(x, y + 1); // 右
  dfs(x, y - 1); // 左
}

2.3 必刷高频题目

题号	题名	核心考点
LC 200	岛屿数量	连通块计数
LC 695	最大岛屿面积	连通块 + 面积统计
LC 463	岛屿周长	邻接边判断
LC 733	图像渲染	泛洪填充（连通块染色）

2.4 核心逻辑

DFS 的唯一作用：“吃掉”整块连通区域（标记为已访问），外层循环遍历网格，每触发一次 DFS 即找到一个新连通块，计数加一。

三、② 路径 DFS（树 / 图）

3.1 适用场景

• 查找所有路径、根到叶路径
• 判断是否存在某条目标路径
• 核心特征：关注「路径细节」，与连通块无关联

3.2 统一模板（含回溯）

function dfs(node, path, res) {
  // 1. 节点为空，直接返回
  if (!node) {
    return;
  }

  // 2. 选择当前节点，加入路径
  path.push(node.val);

  // 3. 到达终点（如：叶子节点），记录答案
  if (!node.left && !node.right) {
    res.push([...path]); // 深拷贝，避免路径被修改
    // 注意：此处不直接return，需先回溯
  }

  // 4. 递归遍历左右子树（树）/ 邻接节点（图）
  dfs(node.left, path, res);
  dfs(node.right, path, res);

  // 5. 回溯：撤销当前选择，恢复路径状态
  path.pop();
}

3.3 必刷高频题目

题号	题名
LC 112	路径总和
LC 113	路径总和 II
LC 257	二叉树的所有路径
LC 797	所有可能的路径

3.4 核心区分

题目出现「所有路径」「所有方案」关键词 → 必须使用「DFS + 回溯」，核心是恢复路径状态，避免不同路径互相干扰。

四、③ 回溯 DFS（枚举解空间）

4.1 适用场景

• 排列、组合、子集问题
• N 皇后、数独等解空间爆炸类题目
• 核心特征：需要枚举所有可能的解，并通过剪枝优化效率

4.2 通用模板

function backtrack(path, start, nums, res) {
  // 1. 满足终止条件，记录答案
  if (满足条件) { // 如：path长度达到要求、找到目标值
    res.push([...path]);
    return;
  }

  // 2. 遍历选择列表
  for (let i = start; i < nums.length; i++) {
    // 剪枝：排除无效选择（可选，优化效率）
    if (需要剪枝的条件) {
      continue;
    }

    // 3. 选择当前元素
    path.push(nums[i]);

    // 4. 递归进入下一层
    backtrack(path, i + 1, nums, res); // 组合/子集用 i+1；排列用 0（需去重）

    // 5. 回溯：撤销选择
    path.pop();
  }
}

4.3 必刷高频题目

题号	题名
LC 46	全排列
LC 47	全排列 II
LC 78	子集
LC 90	子集 II
LC 39	组合总和
LC 51	N 皇后

4.4 核心三件事

1. 选择列表：当前可以选择的元素集合（如：数组中未使用的元素）
2. 终止条件：何时停止递归并记录答案（如：路径长度达标）
3. 剪枝逻辑：如何排除无效选择，减少递归次数（如：跳过重复元素、超出目标值直接终止）

五、④ 边界 DFS

5.1 适用场景

• 二维网格题 + 存在「边界限制」（如：不能接触边界、不能逃出地图）
• 题目特征：未明确声明「网格外是合法值」（与 LC 200 岛屿数量的核心区别）

5.2 标准套路（两步走）

1. 第一步：从边界 DFS，排除非法区域

   // 遍历所有边界点（上下左右四条边）
   const m = grid.length, n = grid[0].length;
   // 上边界 + 下边界
   for (let j = 0; j < n; j++) {
     dfs(0, j);
     dfs(m - 1, j);
   }
   // 左边界 + 右边界（排除已遍历的四个角）
   for (let i = 1; i < m - 1; i++) {
     dfs(i, 0);
     dfs(i, n - 1);
   }

2. 第二步：遍历内部，统计剩余合法区域

   let count = 0;
   for (let i = 1; i < m - 1; i++) {
     for (let j = 1; j < n - 1; j++) {
       if (grid[i][j] === 合法值) {
         dfs(i, j);
         count++;
       }
     }
   }

5.3 必刷高频题目

题号	题名
LC 130	被围绕的区域
LC 1020	飞地的数量
LC 1254	统计封闭岛屿

5.4 与 LC 200 的本质区别

题目	是否声明网格外是水	处理方式
LC 200	是	直接遍历网格统计连通块
LC 130/1020/1254	否	先处理边界，再统计内部

六、DFS 与其他算法快速区分

题目特征	优先算法
连通区域、吞并	DFS
所有路径、所有方案	DFS + 回溯
连续区间（非最值）	双指针
最近距离、层级遍历	BFS
原地删除、去重	快慢指针
区间最值、子串/子数组	滑动窗口

七、DFS 10 秒快速判断流程

1. 是否是网格 / 图类题目？→ 是 → 优先 DFS
2. 是否只关心「连不连」，不关心路径？→ 连通块 DFS
3. 是否要求「所有路径」「所有方案」？→ 路径 DFS + 回溯
4. 是否存在「边界限制」（未声明网格外合法）？→ 边界 DFS（先清边）
5. 否则 → 考虑回溯 DFS（组合/排列/子集）

八、DFS 必刷 12 题清单

1. LC 200 岛屿数量
2. LC 695 最大岛屿面积
3. LC 733 图像渲染
4. LC 112 路径总和
5. LC 113 路径总和 II
6. LC 257 二叉树的所有路径
7. LC 46 全排列
8. LC 78 子集
9. LC 39 组合总和
10. LC 130 被围绕的区域
11. LC 1020 飞地的数量
12. LC 1254 统计封闭岛屿