算法 - 7. 深度优先搜索（DFS）
algorithmstreesgraphsrecursiondfstraversal
By sko•10/6/2025•16 min read
何时使用深度优先搜索（DFS）
当你需要探索所有路径或在回溯前深入探索时使用 DFS。虽然最常用于树遍历，但它也可以适用于：
- 树遍历（经典用例 - 中序、前序、后序）
- 路径查找（检查节点间是否存在路径）
- 连通分量（在网格中寻找岛屿）
- 环检测（检测图中的循环）
- 拓扑排序（对依赖关系排序）
- 回溯问题（生成排列、解决谜题）
- 任何需要在回溯前沿着每个分支尽可能深入探索的问题
示例问题
文件系统探索：给定一个文件夹结构，找到所有具有特定扩展名的文件。你的文件系统如下所示：
root/
├── documents/
│ ├── report.pdf
│ └── notes.txt
├── code/
│ ├── main.js
│ └── utils/
│ └── helper.js
└── images/
└── logo.png找到系统中的所有 .js 文件。
答案：DFS 将探索 root → documents → report.pdf → notes.txt（回溯）→ code → main.js（找到！）→ utils → helper.js（找到！）（回溯）→ images → logo.png。结果：[main.js, helper.js]
最重要的洞察
DFS 承诺在尝试另一条路径之前完全探索一条路径 - 通过递归地深入每个分支直到遇到死胡同，然后回溯以探索替代方案，我们系统地访问每个节点恰好一次而不会错过任何路径。
心理记忆：该算法的天才之处在于使用调用栈作为自然的回溯机制。在每个节点上，我们只需说："处理我自己，然后完全探索我的孩子。"当我们遇到死胡同时，递归会自动处理返回到未探索的分支。
决策框架
在每个节点上，你遵循这个简单的顺序：
- 处理当前节点（何时以及如何处理取决于遍历类型）
- 递归地探索子节点（树的左/右，图的邻居）
- 让递归处理回溯（通过调用栈自动）
唯一的决策是何时处理当前节点：
- 前序：在探索子节点之前处理（根 → 左 → 右）
- 中序：在子节点之间处理（左 → 根 → 右）
- 后序：在探索子节点之后处理（左 → 右 → 根）
何时使用每种遍历类型（简单示例）
前序（根 → 左 → 右）
需要时：你需要在处理子节点之前处理或访问父节点 - 通常是创建副本、打印层次结构，或者当父节点包含子节点所需的信息时。
简单示例：复制文件夹结构 - 当你将文件夹复制到新位置时，你必须：
- 首先创建父文件夹（根）
- 然后复制/创建其子文件夹和文件（子节点）
你不能将文件放在尚不存在的文件夹中！
中序（左 → 根 → 右）
需要时：你需要从二叉搜索树中以排序顺序检索数据，或者当你需要按其自然顺序处理节点时 - 左子树包含较小的值，右子树包含较大的值。
简单示例：在公司树中按薪资打印所有员工，其中：
- 左分支 = 薪资较低的员工
- 当前节点 = 这个员工的薪资
- 右分支 = 薪资较高的员工
中序遍历给你：$50k、$60k、$70k、$80k...完美排序而无需任何排序算法！
后序（左 → 右 → 根）
需要时：你需要在处理父节点之前处理或收集所有子节点的信息 - 通常是删除、计算大小，或者当父节点依赖于子节点的结果时。
简单示例：计算计算机上文件夹的总大小：
- 首先，获取子文件夹 A 中所有文件的大小（左子节点）
- 然后，获取子文件夹 B 中所有文件的大小（右子节点）
- 最后，将它们加在一起得到父文件夹的总大小
在测量所有内容之前，你无法知道文件夹的总大小！
代码
在文件夹结构中查找文件
让我们实现 DFS 来解决一个实际问题：搜索项目文件夹以找到所有 JavaScript 文件。这个例子展示了 DFS 如何深入探索每个文件夹分支，然后再移动到下一个，使用路径栈来跟踪我们的位置并在需要时回溯。
// 实际示例：在文件夹结构中查找特定文件
// 让我们在项目中搜索所有 JavaScript 文件
class FileNode {
constructor(name, isFolder = false) {
this.name = name;
this.isFolder = isFolder;
this.children = [];
}
addChild(child) {
this.children.push(child);
return child;
}
}
// 主要 DFS 算法 - 查找具有特定扩展名的文件
function findFilesWithExtension(rootFolder, extension) {
const foundFiles = [];
const pathStack = []; // 跟踪完整文件路径的当前路径
function searchFolder(node) {
// 基本情况：如果为 null，则没有什么可探索的
if (node == null) {
return;
}
// 将当前项添加到路径
pathStack.push(node.name);
const currentPath = pathStack.join('/');
// DECISION FRAMEWORK: 检查这是否是我们要找的
const isTargetFile = !node.isFolder && node.name.endsWith(extension);
if (isTargetFile) {
foundFiles.push(currentPath);
}
// 递归探索所有子节点（深入！）
for (const child of node.children) {
searchFolder(child); // 完全深入这个子节点
}
// 回溯：探索完成后从路径中删除当前项
pathStack.pop();
}
searchFolder(rootFolder);
return foundFiles;
}
// 构建我们的示例文件系统
const root = new FileNode('project', true);
// 添加包含 JavaScript 文件的 src 文件夹
const src = root.addChild(new FileNode('src', true));
src.addChild(new FileNode('index.js'));
src.addChild(new FileNode('app.js'));
const components = src.addChild(new FileNode('components', true));
components.addChild(new FileNode('Button.js'));
components.addChild(new FileNode('Button.css')); // 不是 JS 文件
// 添加包含 markdown 文件的 docs 文件夹
const docs = root.addChild(new FileNode('docs', true));
docs.addChild(new FileNode('README.md'));
docs.addChild(new FileNode('guide.md'));
// 在根目录添加配置文件
root.addChild(new FileNode('package.json'));
root.addChild(new FileNode('config.js'));
// 查找所有 JavaScript 文件
const jsFiles = findFilesWithExtension(root, '.js');
console.log('找到的 JavaScript 文件：');
console.log(jsFiles);
// 输出：
// [
// 'project/src/index.js',
// 'project/src/app.js',
// 'project/src/components/Button.js',
// 'project/config.js'
// ]
// 让我们追踪一条路径来看 DFS 的实际操作：
// 1. 从 'project' 开始
// 2. 转到第一个子节点 'src'（深入探索！）
// 3. 转到 'src' 的第一个子节点 'index.js'（更深！）
// 4. 'index.js' 没有子节点，处理它，回溯
// 5. 转到 'src' 的下一个子节点 'app.js'（探索兄弟）
// 6. 'app.js' 没有子节点，处理它，回溯
// 7. 转到 'src' 的下一个子节点 'components'（深入新分支）
// ... 如此继续可视化三种遍历顺序
让我们使用一棵简单的树来看看每种遍历顺序如何以不同方式访问节点：
A
/ \
B C
/ \
D E使用这个树结构，每种遍历类型将根据它何时相对于子节点处理父节点，以不同的顺序访问节点。
class SimpleNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 前序：在子节点之前处理节点（根 → 左 → 右）
function preOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
// DECISION FRAMEWORK: 首先处理当前
result.push(current.value);
traverse(current.left); // 然后向左
traverse(current.right); // 然后向右
}
traverse(node);
return result;
}
// 中序：在子节点之间处理节点（左 → 根 → 右）
function inOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // 首先向左
// DECISION FRAMEWORK: 在中间处理当前
result.push(current.value);
traverse(current.right); // 然后向右
}
traverse(node);
return result;
}
// 后序：在子节点之后处理节点（左 → 右 → 根）
function postOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // 首先向左
traverse(current.right); // 然后向右
// DECISION FRAMEWORK: 最后处理当前
result.push(current.value);
}
traverse(node);
return result;
}
// 构建示例树
const tree = new SimpleNode('A');
tree.left = new SimpleNode('B');
tree.right = new SimpleNode('C');
tree.left.left = new SimpleNode('D');
tree.left.right = new SimpleNode('E');
console.log('\n遍历顺序：');
console.log('前序 (根-左-右):', preOrder(tree)); // [A, B, D, E, C]
console.log('中序 (左-根-右):', inOrder(tree)); // [D, B, E, A, C]
console.log('后序 (左-右-根):', postOrder(tree)); // [D, E, B, C, A]
// 每种遍历的实际含义：
// 前序：创建树的副本（在子节点之前处理父节点）
// 中序：从 BST 获取排序的值（左 < 根 < 右）
// 后序：安全地删除树（在父节点之前删除子节点）疑惑破除
常见疑惑："DFS 不会陷入无限循环或重访节点吗？如果我有一个带环的图，或者如果树实际上很巨大 - 我们不会耗尽内存吗？"
为什么你可能认为 DFS 会失败
考虑探索一个人们可以互相成为朋友的社交网络（创建环）：
Alice → Bob → Charlie
↑ ↓
└─────────────┘你可能会担心：
- "如果我们从 Alice 开始，到 Bob，然后 Charlie，然后回到 Alice...我们就永远被困住了！"
- "如果树有 1000 层深怎么办？调用栈不会溢出吗？"
- "我们如何知道不会多次处理同一个节点？"
为什么这种想法是不完整的
关键认识：DFS 对这些担忧有两个简单的解决方案：
- 对于环：使用访问集来跟踪已探索的节点
- 对于深度：调用栈空间是 O(高度)，而不是 O(节点)
让我们看看如何处理带环的图：
function dfsGraph(startNode, graph) {
const visited = new Set();
const result = [];
function explore(node) {
// 防止重访 - 这打破了环！
if (visited.has(node)) {
return;
}
visited.add(node);
result.push(node);
// 探索所有未访问的邻居
for (const neighbor of graph[node]) {
explore(neighbor);
}
}
explore(startNode);
return result;
}
// 带环图的示例
const socialNetwork = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Charlie'],
'Charlie': ['Alice'] // 创建环！
};
console.log(dfsGraph('Alice', socialNetwork));
// ['Alice', 'Bob', 'Charlie'] - 没有无限循环！具体示例：DFS 有效处理所有树形状
让我们追踪不同的树形状来看看为什么 DFS 是健壮的：
极深的树（链表形状）：
1 → 2 → 3 → 4 → ... → 1000- 空间复杂度：调用栈的 O(1000)
- 但我们仍然恰好访问所有 1000 个节点一次
- 现代系统可以轻松处理数千个递归调用
极宽的树：
1
/ / | \ \
2 3 4 5 6 (1000 个子节点)- 空间复杂度：O(2) - 只是当前路径深度！
- 我们完全探索子节点 2，回溯，然后子节点 3，等等
- 永远不需要同时存储所有兄弟节点
平衡树：
1
/ \
2 3
/ \ / \
4 5 6 7- 平衡树的空间复杂度：O(log n)
- 递归探索的最有效情况
为什么是 O(log n)？ 在具有 n 个节点的平衡树中，高度是 log₂(n)。例如，具有 1,000,000 个节点的平衡树的高度只有约 20 层。由于 DFS 只在内存中保留当前路径（而不是所有节点），即使有一百万个节点，调用栈也从不超过 20 帧！
数学证明：为什么空间复杂度是 O(log n)
让我们逐步证明为什么平衡二叉树中 n 个节点具有高度 log₂(n)：
步骤 1：理解平衡二叉树的结构
- 每一层 i 最多有 2^i 个节点（第 0 层有 1 个，第 1 层有 2 个，第 2 层有 4 个，等等）
- 高度为 h 的完全平衡树恰好有 2^(h+1) - 1 个节点
步骤 2：推导节点数（n）和高度（h）之间的关系
对于高度为 h 的平衡树：
- 最大节点数 = 1 + 2 + 4 + 8 + ... + 2^h
- 这是一个几何级数 = 2^(h+1) - 1
因此：n ≤ 2^(h+1) - 1为什么 n ≤ 2^(h+1) - 1？ 这个不等式表示高度为 h 的二叉树的最大节点数：
- 每一层 i 最多可以有 2^i 个节点
- 总节点数 = 2^0 + 2^1 + 2^2 + ... + 2^h（所有层的总和）
- 使用几何级数公式：和 = a(r^n - 1)/(r - 1)，其中 a=1，r=2，n=h+1
- 结果：n = (2^(h+1) - 1)/1 = 2^(h+1) - 1
我们使用 ≤（不等号）而不是 =（等号）是因为树在最后一层可能没有完全填满。例如，下面两个高度为 2 的树都是有效的：
完全树 (n = 7): 不完全树 (n = 4):
1 1
/ \ / \
2 3 2 3
/ \ / \ /
4 5 6 7 4继续推导：
n + 1 ≤ 2^(h+1)
log₂(n + 1) ≤ h + 1
h ≥ log₂(n + 1) - 1
由于 h 必须至少为 log₂(n)，我们说 h = O(log n)步骤 3：用实际数字的具体示例
具有 7 个节点的树（完全平衡）：
1 高度 = 2
/ \ 每层的节点：
2 3 第 0 层：1 个节点
/| |\ 第 1 层：2 个节点
4 5 6 7 第 2 层：4 个节点
总计：7 个节点 = 2^3 - 1
高度：2 = floor(log₂(7)) ✓
具有 1,000,000 个节点的树：
log₂(1,000,000) ≈ 19.93
高度 ≈ 20 层
具有 1,000,000,000 个节点的树（10 亿）：
log₂(1,000,000,000) ≈ 29.9
高度 ≈ 30 层步骤 4：为什么这对 DFS 空间复杂度很重要
DFS 只在调用栈上存储从根到当前节点的当前路径：
DFS 遍历期间的调用栈：
[root] → 1 帧（在根节点）
[root, left] → 2 帧（在左子节点）
[root, left, left.left] → 3 帧（在 left.left 子节点）
...
[root, ..., leaf] → h+1 帧（在最深的叶节点）
最大栈帧 = 高度 + 1 = 平衡树的 O(log n)节点数对比高度的可视化比较：
节点数 (n) | 高度 (h) | 所需栈帧
------------- | -------- | ----------------
7 | 2 | 3
15 | 3 | 4
31 | 4 | 5
1,023 | 9 | 10
1,048,575 | 19 | 20
1,073,741,823 | 29 | 30注意即使有超过十亿个节点，我们也只需要 30 个栈帧！这就是对数增长的威力 - 高度的增长比节点数慢得多。
为什么调用栈是我们的朋友
DFS 的精妙之处在于调用栈自动提供：
- 返回位置的记忆 - 当我们完成探索一个分支时，栈确切地知道我们在哪里停止
- 隐式回溯 - 无需手动跟踪"回到哪里"
- 自然的深度限制 - 栈溢出实际上是防止无限递归的功能
每个递归调用只向栈添加一帧：
explore(root) // 栈：[root]
explore(left) // 栈：[root, left]
explore(left.left) // 栈：[root, left, left.left]
return // 栈：[root, left] - 自动回溯！
explore(left.right) // 栈：[root, left, left.right]
return // 栈：[root, left]
return // 栈：[root]
explore(right) // 栈：[root, right]保证：每个节点恰好被访问一次，使用的最大内存与树的高度成正比，而不是其总大小。对于图，访问集确保我们永远不会处理一个节点两次，完全消除了无限循环。