深度搜索思路

面试回答： DFS（深度优先搜索）会沿一条路径尽可能深入，走不下去就返回上一层，继续探索其他分支。递归调用栈记录返回位置；DFS 内的循环枚举当前状态的下一步，DFS 外的循环枚举搜索起点。图遍历通常用 visited 防止重复访问，枚举方案时则常配合回溯恢复路径状态。

1. 核心思路：先深入，再返回

    A
   / \
  B   C
 / \
D   E

先访问当前节点，再从左到右搜索，顺序是 A → B → D → E → C。

进入 dfs(B) 后，dfs(A) 会暂停，等待 B 的整个分支搜索完成。因此访问 D 后返回 B，继续访问 E；B 的分支全部完成后才回到 A，访问 C。

进入当前状态 → 处理当前状态 → 选择一个分支 → 递归深入
                              ↑                ↓
                         继续下一个分支 ← 返回

写代码前先确定：参数表示什么状态？什么时候停止？下一步有哪些选择？ 如果多个分支共享可变状态，还要确定返回后需要恢复什么。

2. 树的 DFS 模板

以下示例均使用 JavaScript；树节点约定为 { val, left, right }，空节点为 null。

function preorder(root) {
  const result = [];

  function dfs(node) {
    if (node == null) return; // 终止条件

    result.push(node.val);    // 处理当前节点
    dfs(node.left);           // 探索左分支
    dfs(node.right);          // 探索右分支
  }

  dfs(root);                  // 从根节点开始
  return result;
}

处理节点的位置决定遍历顺序：

处理位置遍历方式顺序
两次递归之前前序根 → 左 → 右
两次递归之间中序左 → 根 → 右
两次递归之后后序左 → 右 → 根

真正的树沿子节点向下不会重复到达某个节点，因此通常不需要 visited。如果把树存成无向邻接表，就需要排除父节点或使用访问标记，避免沿边返回。

3. 图的 DFS 模板

图可能有环，也可能多条路径通向同一个节点。若不标记，会重复处理，甚至无限递归。

function traverseFrom(graph, start) {
  const visited = new Set();
  const result = [];

  function dfs(node) {
    visited.add(node); // 先标记，再探索邻居
    result.push(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  dfs(start);
  return result;
}

const graph = new Map([
  ["A", ["B"]],
  ["B", ["A", "C"]],
  ["C", ["B"]],
  ["D", ["E"]],
  ["E", ["D"]],
]);

console.log(traverseFrom(graph, "A")); // ["A", "B", "C"]

一次 DFS 只覆盖从起点可达的节点，不一定覆盖整个图。

4. for 应该放在哪里？

“DFS 内使用 for”和“在 for 内调用 DFS”并不互斥：DFS 内的循环通常就会调用 DFS。真正要区分的是循环位于递归函数内部，还是位于递归入口外部。

循环位置枚举什么要解决的问题典型场景
DFS 内部当前状态的下一步从这里往哪走？图的邻居、网格四个方向、排列的可选元素
DFS 外部搜索起点从哪里开始走？遍历不连通图、统计岛屿

DFS 内的 for：逐个探索分支

function dfs(node) {
  visited.add(node);

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      dfs(neighbor);
    }
  }
}

这是局部模板，graph 和 visited 由外层提供。循环枚举同一层的选择，递归进入下一层；前一个递归调用返回后，循环才会继续下一个邻居。

二叉树不写 for，只是因为分支固定，可以直接展开。对前序遍历而言，下面两种写法等价：

// 写法一：固定的两个分支
dfs(node.left);
dfs(node.right);

// 写法二：用循环枚举这两个分支
for (const child of [node.left, node.right]) {
  dfs(child);
}

两种写法任选其一，dfs 内需要处理空节点。是否使用 for 取决于如何表达分支，不取决于“这是不是 DFS”。

DFS 外的 for：补齐搜索起点

对上面的无向图，dfs("A") 访问不到 D、E。完整遍历需要外层循环寻找尚未访问的起点：

function traverseAll(graph) {
  const visited = new Set(); // 多个起点共享访问记录
  const result = [];

  function dfs(node) {
    visited.add(node);
    result.push(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
  }

  // 约定 graph 包含所有节点，包括孤立节点
  for (const node of graph.keys()) {
    if (!visited.has(node)) dfs(node);
  }

  return result;
}

外层检查的是“有没有访问过”，不是每次都重新遍历。若只是遍历一棵树，从根节点调用一次即可。

5. 两种循环同时出现：岛屿数量

外层循环寻找新岛屿的起点，内部循环探索当前格子的四个方向。一轮 DFS 会标记整座岛，后续扫描到它的其他格子时会跳过。

function numIslands(grid) {
  if (grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const visited = new Set();
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let count = 0;

  function dfs(r, c) {
    visited.add(r * cols + c); // 数字键唯一标识格子

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        grid[nr][nc] === "1" &&
        !visited.has(nr * cols + nc)
      ) {
        dfs(nr, nc);
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1" && !visited.has(r * cols + c)) {
        count++;  // 发现一座尚未访问的岛
        dfs(r, c);
      }
    }
  }

  return count;
}

console.log(numIslands([
  ["1", "1", "0"],
  ["0", "0", "1"],
])); // 2

示例约定输入是规则矩形，使用字符串 "1" 表示陆地，且只有上下左右相连才算同一座岛。不要直接用 Set 保存新建的 [r, c] 数组来查重：JavaScript 按引用比较数组，两次创建的 [1, 2] 不是同一个键。

6. 搜索所有方案：DFS + 回溯

枚举排列、组合或路径时，不同分支常共享 path，需要在返回后撤销本次选择，避免影响下一个分支。

// 教学伪代码：辅助函数由具体题目实现
function solve(initialState) {
  const result = [];
  const path = [];

  function dfs(state) {
    if (isComplete(state)) {
      result.push([...path]); // 保存当前路径的快照
      return;
    }

    for (const choice of getChoices(state)) {
      if (!isValid(state, choice)) continue;

      path.push(choice); // 做选择
      dfs(nextState(state, choice)); // 假设返回新状态，不修改 state
      path.pop();        // 撤销选择
    }
  }

  dfs(initialState);
  return result;
}

这个模板假设答案只在终止状态收集；子集等问题也可能需要在每次进入 DFS 时收集答案。如果同时修改了共享的 used 或其他状态，也必须恢复。完整实例见 回溯算法模板。

标记的含义返回后是否撤销原因
普通图遍历的 visited通常不撤销已处理节点不需要再次处理
枚举简单路径时的路径内标记通常撤销只禁止当前路径重复使用，其他路径仍可使用

DFS 是搜索顺序；回溯是在探索分支后恢复状态。不是所有 DFS 都需要手动撤销选择。

7. 复杂度与常见错误

  • 树遍历： 时间 O(n)，递归栈空间 O(h)，h 是树高；若保存全部结果，还需要 O(n) 结果空间。
  • 邻接表图遍历： 完整遍历时间 O(V + E)，访问标记与递归栈额外空间 O(V)。外层循环不会让已访问分量反复搜索。
  • 岛屿数量： 时间和最坏额外空间均为 O(rows × cols)。
  • 枚举方案： 复杂度取决于搜索树大小和复制答案的成本，不能直接套用普通图遍历的线性复杂度。
  • 递归过深： JavaScript 可能发生调用栈溢出，可改用显式栈实现 DFS；每个栈帧本质上保存当前状态和后续执行位置。
常见错误说法或写法修正
“有 for 就是 BFS”搜索顺序才是关键；递归完成一个分支再处理下一个仍然是 DFS
“DFS 必须写 for”固定分支可以直接写多次递归调用
“每次 DFS 后都要清除 visited”先明确标记代表全局已访问，还是当前路径已使用
递归邻居之后才标记当前节点图中可能沿环返回；应在探索邻居之前标记
在外层循环每次重建 visited完整图遍历应共享标记，否则会重复搜索
使用 result.push(path) 保存答案应复制数组，否则多个答案引用同一个可变路径；元素为可变对象时还需考虑对象复制

8. 递进追问

追问参考答案考察目的与回答重点
1. DFS 为什么叫深度优先？一个分支尚未返回时，先继续探索该分支的下一层。考察定义是否落实到执行顺序
2. 递归返回后为什么能继续下一个邻居？调用栈保留了当前函数的局部状态和返回位置。考察底层机制，抓住暂停与恢复
3. DFS 内的 for 有什么作用？枚举当前状态的所有候选分支，逐个递归。考察循环与递归的分工
4. 为什么还需要外层 for？一个起点可能无法覆盖所有节点，外层寻找未访问的起点。考察可达范围与完整遍历的区别
5. 图的 visited 为什么不撤销？它记录全局已处理节点，撤销会导致重复搜索。考察状态语义，不能机械套用回溯模板
6. 空网格和超长链如何处理？空网格提前返回；超长链可用显式栈避免递归栈溢出。考察边界和工程限制
7. DFS 和 BFS 如何选？DFS 适合深入探索和回溯，BFS 按层推进，常用于无权图最短路径。考察搜索顺序与问题目标的匹配
8. 如何用于项目中的依赖图检查？DFS 探索依赖；有向环检测需区分未访问、当前递归路径中、已完成三种状态。考察迁移能力，单个 visited 不足以判定有向环

9. 复习提纲

  • 关键词： 深入、调用栈、分支、起点、状态恢复。
  • 一句话本质： 循环决定当前有哪些路，递归负责沿一条路深入，返回后继续其他路。
  • 可迁移场景： 树遍历、图连通性、网格搜索、排列组合、依赖分析。
  • 1 分钟回答： 讲清 DFS 顺序与内外循环分工。
  • 3 分钟回答： 补充树和图模板、visited 的作用以及岛屿例子。
  • 10 分钟回答： 展开回溯状态恢复、复杂度、递归栈限制与有向环检测。

自测时可依次回答：为什么树可以不写 for？为什么统计岛屿要有外层循环？为什么枚举路径和普通图遍历对访问标记的处理不同？