12.2　深度优先搜索

学习目标：学完本节，你能

• 写出 DFS 的递归版和迭代版；
• 说清 visited 标记为什么是必需的 —— 以及没有它会怎样；
• 说出 DFS 能回答哪些问题（以及它不能回答什么）。

先修：9.2（树的深度优先遍历）、11.1（图的表示）。 固定术语：深度优先搜索、访问标记、回溯。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：走迷宫时"左手贴墙法"

DFS 的策略：认准一个方向走到底，走不通了再退回来试另一条。

用走迷宫打比方：

• DFS：一只手贴着墙一直走 —— 遇到岔路随便选一条，走到底；死路就退回上一个岔路口，换一条没走过的。
• BFS（12.3 节）：像水波纹一样，从起点一圈一圈向外扩散。

9.2 节已经用树的遍历演示过 DFS。但图比树多了一个关键区别：

这一条区别是本节的核心 —— 图的 DFS 如果忘了 visited 标记，会陷入死循环。

二、图的例子

本节用这个图（无向图）：

        0 —— 1
        |  \  |
        |   \ |
        2 —— 3
        |
        4

邻接表：

  0->[1,2,3]   1->[0,3]   2->[0,3,4]   3->[0,1,2]   4->[2]

三、递归版 DFS

var visited = new bool[graph.VertexCount];

void DfsRecursive(int v, int depth)
{
    visited[v] = true;                    // ★ 一进来就标记
    Console.WriteLine($"访问 {v}");

    foreach (int next in graph.Neighbors(v))
    {
        if (!visited[next])               // 只走没访问过的邻居
        {
            DfsRecursive(next, depth + 1);
        }
    }
}

实测追踪（从 0 出发）：

    访问 0
      从 0 走向 1
      访问 1
        从 1 走向 3
        访问 3
          从 3 走向 2
          访问 2
            从 2 走向 4
            访问 4

  访问顺序: 0 -> 1 -> 3 -> 2 -> 4

跟着走一遍：

注意第 5～9 步的"返回" —— 这就是 DFS 的"回程"（2.1 节讲过）。

去程走到底，回程一路退回来，直到找到还没走过的岔路。

本例中回程一路退到 0 都没找到新路，所以整个遍历结束。

四、visited 为什么是必需的

假设去掉 visited 标记，用同一个图从 0 出发：

  访问 0
    访问 1
      访问 0        ← 又回到 0 了！
        访问 1
          访问 0    ← 无限循环……

因为有环（0—1—3—0 就是一个环），DFS 会绕圈绕到天荒地老。

visited 标记的作用就是"记住来过这里了，别再走了"。

树不需要它 —— 因为树没有环，从根往下走永远到不了已经走过的节点。

标记的时机很关键：

void Dfs(int v)
{
    visited[v] = true;        // ★ 必须在【进入时】立刻标记
    foreach (int next in graph.Neighbors(v))
        if (!visited[next]) Dfs(next);
}

如果放在循环里（访问完邻居之后才标记），同一个节点可能被多个邻居重复访问，导致重复遍历甚至栈溢出。

实测的复杂度印证：

  访问了 100,000 个顶点，耗时 1.9 ms

$O(V + E)$：

• 每个顶点最多被访问一次 —— 因为有 visited
• 每条边最多被检查两次（无向图，从两端各看一次）

五、迭代版 DFS

递归版有栈溢出风险（2.2 节）。改成用显式栈：

List<int> DfsIterative(int start)
{
    var result = new List<int>();
    var seen = new bool[graph.VertexCount];
    var stack = new Stack<int>();

    stack.Push(start);

    while (stack.Count > 0)
    {
        int v = stack.Pop();
        if (seen[v]) continue;          // 可能被重复压栈，跳过已访问的
        seen[v] = true;
        result.Add(v);

        // 关键：为了和递归版顺序【尽量一致】，要【逆序】压栈
        //（因为栈是后进先出，逆序压入才能顺序弹出）
        var neighbors = graph.Neighbors(v);
        for (int i = neighbors.Count - 1; i >= 0; i--)
        {
            if (!seen[neighbors[i]]) stack.Push(neighbors[i]);
        }
    }
    return result;
}

实测：0 -> 1 -> 3 -> 2 -> 4 —— 和递归版一致 ✓

一个容易忽略的细节：逆序压栈

栈是后进先出。如果按 0,1,2,3 的顺序压栈，弹出顺序是 3,2,1,0 —— 反了。

所以要先逆序遍历邻居再压栈，才能得到和递归版一样的顺序。

实测不逆序的结果：

  如果不逆序压栈: 0 -> 3 -> 2 -> 4 -> 1
  和递归版一致: False

但要注意：两者【都是合法的 DFS】。

访问顺序不同，但都满足"一条路走到底"的语义。

这说明一件重要的事：图的 DFS 顺序【不唯一】 —— 它取决于"你以什么顺序访问邻居"。

树的遍历顺序为什么是唯一的？ 因为树的孩子有明确的"左/右"之分；而图的邻居只是一个集合，没有内在顺序。

六、DFS 的经典应用：找路径

"从 A 能不能走到 B？如果能，走哪条路？"

List<int>? FindPath(int from, int to)
{
    var path = new List<int>();
    var seen = new bool[graph.VertexCount];

    bool Dfs(int v)
    {
        seen[v] = true;
        path.Add(v);                       // 假设这个点在路径上

        if (v == to) return true;

        foreach (int next in graph.Neighbors(v))
        {
            if (!seen[next] && Dfs(next)) return true;
        }

        path.RemoveAt(path.Count - 1);     // ★ 回溯：这条路走不通，退回来
        return false;
    }

    return Dfs(from) ? path : null;
}

实测：

  0 到 4 的路径: 0 -> 1 -> 3 -> 2 -> 4
  1 到 4 的路径: 1 -> 0 -> 2 -> 4
  3 到 2 的路径: 3 -> 0 -> 2

注意 path.RemoveAt 那一行 —— 那就是【回溯】（9.4 节讲过）。

DFS 找路径的本质是"一条路试到底，不行就退回来换一条"。

看 1 到 4 的路径：DFS 从 1 出发，先走了 1 → 0（因为 0 是 1 的第一个邻居），然后从 0 走到 2，再到 4。

它没有选择更短的 1 → 3 → 2 → 4 —— 因为 DFS 只保证"找到一条"，不保证最短。

要最短路径，用 BFS（下一节）。

七、DFS 能回答什么、不能回答什么

实测：

  从 0 出发能到达: 0, 1, 2, 3, 4
  能否到达 4？True
  能否到达 99？（不存在的顶点）False

"DFS 不保证最短"这一点很关键 —— 它是 DFS 和 BFS 最本质的区别。

记忆方法：

• DFS 回答"能不能到"
• BFS 回答"最少几步到"

八、练习

练习 12.2.1（手写 DFS） 对下面的图，从顶点 0 出发做 DFS，写出访问顺序（假设邻居按编号从小到大访问）。

  0 —— 1 —— 4
  |    |
  2 —— 3

练习 12.2.2（判断 visited 的位置） 下面两个 DFS 实现，哪个是正确的？为什么？

// 版本 A
void DfsA(int v)
{
    visited[v] = true;
    result.Add(v);
    foreach (int next in graph.Neighbors(v))
        if (!visited[next]) DfsA(next);
}

// 版本 B
void DfsB(int v)
{
    result.Add(v);
    foreach (int next in graph.Neighbors(v))
        if (!visited[next]) { visited[next] = true; DfsB(next); }
}

练习 12.2.3（判断） 判断对错并说明理由： (a) 图的 DFS 访问顺序是唯一的。 (b) DFS 不需要 visited 标记，只要图没有环。 (c) DFS 找到的路径一定是最短的。 (d) DFS 的复杂度是 $O(V + E)$。

练习 12.2.4（工程判断） 一个 IDE 要做"查找所有引用"功能：给定一个函数名，找出代码库里所有调用它的地方（包括间接调用）。 (a) 这应该用 DFS 还是 BFS？ (b) 为什么？ (c) 如果代码库有循环依赖（A 调用 B，B 调用 A），会有什么问题？怎么解决？

练习 12.2.5（挑战·迭代版为什么需要"重复压栈"） 本节的迭代版 DFS 里有一行 if (seen[v]) continue; —— 说明同一个顶点可能被多次压入栈。

(a) 举一个具体的例子，说明什么情况下会重复压栈。 (b) 能不能在压栈时就标记 visited，从而避免重复压栈？这样改有什么问题？ (c) 两种做法的时间复杂度一样吗？

九、练习答案

12.2.1

图的结构：

  0 —— 1 —— 4
  |    |
  2 —— 3

邻接表：0->[1,2]，1->[0,3,4]，2->[0,3]，3->[1,2]，4->[1]

DFS 过程（邻居按编号从小到大）：

访问顺序：0 → 1 → 3 → 2 → 4

注意第 4～5 步的"回退" —— 从 2 退回 3、再退回 1，然后才继续探索 1 的下一个邻居（4）。

这就是"一条路走到底，再退回来试别的"。

12.2.2

版本 A 是正确的。

关键区别：标记 visited 的时机。

版本 B 的具体问题：

1. 起点没被标记：DfsB(start) 直接被调用，visited[start] 始终是 false。

   后果：如果图里有一个环绕回起点，会再次访问起点，造成重复甚至无限循环。

2. 语义混乱：标记"下一个要访问的节点"，而不是"当前正在访问的节点" —— 这让代码很难推理。

修复版本 B：

void DfsB(int v)
{
    if (visited[v]) return;         // 进来先检查
    visited[v] = true;              // 再标记
    result.Add(v);
    foreach (int next in graph.Neighbors(v))
        DfsB(next);
}

这条经验的通用形式："标记"和"检查"必须配套，而且要在同一个地方完成。

版本 B 把"检查"放在调用方、"标记"也放在调用方，导致被直接调用的起点绕过了这套逻辑。

更稳妥的写法是"谁负责处理，谁负责标记" —— 也就是版本 A 的形式。

12.2.3

• (a) 错。 本节实测：同一个图、同样的起点，逆序压栈得到 0 → 1 → 3 → 2 → 4，顺序压栈得到 0 → 3 → 2 → 4 → 1。

  两者都是合法的 DFS。

  根本原因：图的邻居是一个集合，没有内在顺序；而树的"左孩子/右孩子"是有序的，所以树的遍历顺序唯一。

  实践含义：如果你依赖 DFS 的访问顺序（比如"找到的第一条路径"），必须先明确邻居的遍历顺序。

• (b) 错（说法有歧义）。 如果图确实没有环（是一棵树或森林），那确实不需要 visited。

  但问题是：你事先怎么知道图没有环？

  • 如果图是给定的、你检查过 → 那可以省
  • 如果图来自外部输入 → 必须假设它可能有环

  工程上的正确做法：永远加 visited。它的代价只是一个布尔数组（$O(V)$ 空间），而漏掉它的代价是死循环。

  "防御性编程"在这里很划算。

• (c) 错。 DFS 只保证"找到一条"，不保证最短。 >

  必然反例：考虑这样一张图 ——

    0 —— 1 —— 2 —— 3 —— ... —— 100      （一条长链）
    |
    +—————————————————————————— 100      （从 0 直达 100 的捷径）
  

  DFS 从 0 出发：如果它先访问了邻居 1（按编号顺序就会这样），就会沿着长链一路走到底， 走满 100 步才到达 100。

  而最短路径是 0 → 100，只要 1 步。

  根本原因：DFS 一旦找到目标就立刻返回，它从不比较"是不是还有更短的路"。

  要最短路径，必须用 BFS（12.3 节）—— 因为 BFS 是"一层一层"扩散的，第一次到达某个顶点时，走的一定是最少步数。

• (d) 对。 每个顶点最多访问一次，每条边最多检查两次（无向图），所以是 $O(V + E)$。

12.2.4

(a) 应该用 DFS。

(b) 理由：

1. 需要的是"全部"而不是"最短" —— DFS 会系统地走遍所有可达节点，而 BFS 的"层"信息在这里没有意义。
2. 递归深度对应调用链 —— 用 DFS 时，调用栈本身就记录了"谁调用了谁"的路径，这正好是你需要展示给用户的信息（"这里通过 A→B→C 间接调用"）。
3. 内存开销更小 —— BFS 的队列在"层级很宽"时（一个函数被很多地方调用）会迅速膨胀；而 DFS 只需要深度那么大的栈。

(c) 循环依赖会导致死循环 —— 必须用 visited 解决。

void FindReferences(string functionName, HashSet<string> visited, List<string> result)
{
    if (!visited.Add(functionName)) return;    // ★ 已经找过了，直接返回
    result.Add(functionName);

    foreach (var caller in FindCallers(functionName))
        FindReferences(caller, visited, result);
}

visited 用 HashSet<string> 而不是 bool[] —— 因为顶点是字符串（函数名），不是连续编号。

这也是 12.1 节说的"邻接表用 Dictionary"的实际场景 —— 真实工程里顶点往往不是整数。

12.2.5

(a) 重复压栈的例子：

考虑菱形结构 0 → 1 → 3 和 0 → 2 → 3（0 连着 1 和 2，1 和 2 都连着 3）。

      0
     / \
    1   2
     \ /
      3

处理 0 时：把 1 和 2 都压栈（此时 3 还没被访问）。

假设栈是 [1, 2]（2 在栈顶）：

1. 弹出 2，标记 2，把 2 的邻居 3 压栈 → 栈 [1, 3]
2. 弹出 3，标记 3 → 栈 [1]
3. 弹出 1，标记 1 → 把 1 的邻居 3 压栈（3 已经在 seen 里了，所以这行 if (!seen[neighbors[i]]) 会挡住）

嗯，这个例子里没重复。

举一个具体的例子（菱形图）：

      0
     / \
    1   2
     \ /
      3

邻接表：0->[1,2]，1->[0,3]，2->[0,3]，3->[1,2]

按本节的实现（弹出时标记 + 逆序压栈）走一遍：

第 3 步就是重复压栈发生的地方 —— 3 把 2 压了进去，但栈里原本就有一个 2 在等着。

根本原因："弹出时才标记"意味着"压栈时不检查是否已访问"——

只要一个顶点在被弹出之前又被另一个顶点当作邻居压了一次，栈里就会出现两份。

if (seen[v]) continue; 就是用来兜住这种情况的。

(b) 能不能在压栈时标记？

能，但会改变 DFS 的语义。

// 压栈时就标记
stack.Push(start);
seen[start] = true;                    // ★ 起点立即标记
while (stack.Count > 0)
{
    int v = stack.Pop();
    result.Add(v);                     // 不需要再检查了
    foreach (int next in graph.Neighbors(v))
    {
        if (!seen[next])               // 检查后立即标记
        {
            seen[next] = true;
            stack.Push(next);
        }
    }
}

这样确实不会重复压栈了。但问题是：

访问顺序会变。

"弹出时标记"的顺序 = 真正的 DFS 顺序（和递归版一致）； "压栈时标记"的顺序 = 一种"提前预定"的顺序，更接近 BFS 的变体。

具体来说：压栈时标记，意味着"我决定要去访问它了"；而弹出时标记，意味着"我真的正在访问它"。

递归版 DFS 是"进入时标记" —— 对应的是"弹出时标记"（因为递归调用 ≈ 压栈 + 立即执行）。

(c) 时间复杂度一样，都是 $O(V + E)$。

但有细微差别：

空间上的差别值得一提：弹出时标记可能导致栈里堆积大量重复元素，最坏情况下栈的大小能到 $O(E)$（每条边都可能压一次）。

但对绝大多数图，两者的实际差别很小，而且弹出时标记的顺序更符合 DFS 的直觉（和递归版一致）。

实践建议：用"弹出时标记"，并保留 if (seen[v]) continue; —— 这是最不容易出错、且和递归版语义一致的写法。

十、常见错误

十一、本节总结

1. DFS = 一条路走到底，走不通再退回来。 用递归或显式栈实现。
2. visited 标记是 DFS 的灵魂 —— 图有环，没有它会无限绕圈。树的遍历不需要它，图的必须有。
3. 标记必须在"进入时"，而不是在调用方 —— 否则起点会被漏掉。
4. 图的 DFS 顺序不唯一：实测逆序压栈得 0→1→3→2→4，顺序压栈得 0→3→2→4→1，都合法。
5. 迭代版要处理"重复压栈"：if (seen[v]) continue; 不能省。
6. DFS 找路径用回溯：path.Add 在递归前、path.RemoveAt 在递归后。它找到的是"一条"路径，不是最短的。
7. 复杂度 $O(V + E)$：每个顶点访问一次、每条边检查两次。实测 10 万顶点 1.9 ms。
8. DFS 回答"能不能到"，BFS 回答"最少几步到" —— 这是两者的本质区别。

下一节衔接：本节最后反复提到"DFS 不保证最短"。那么怎么才能找到最短路径？答案是换成"一圈一圈扩散"的 BFS。它在 9.3 节已经以"树的层序遍历"出现过，现在要推广到图上 —— 而且这次有一个新的、非常重要的性质：BFS 找到的路径一定是最短的。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "12.2",
  "title": "深度优先搜索",
  "covered": [
    "DFS 的走迷宫直觉与「图有环、树没有」的关键区别",
    "递归版 DFS 完整实现与九步追踪",
    "visited 标记的必要性（去掉会无限循环）与标记时机",
    "迭代版 DFS 的实现与逆序压栈技巧",
    "实测：逆序压栈顺序与递归版一致，顺序压栈得到另一个合法顺序",
    "「图的 DFS 顺序不唯一」的论证",
    "DFS 找路径的回溯实现与实测（三条路径）",
    "DFS 能回答/不能回答的问题对照表",
    "复杂度 O(V+E) 实测（10 万顶点 1.9ms）"
  ],
  "unresolved": [
    "BFS 与最短路径留到 12.3",
    "连通分量与环检测留到 12.4",
    "回溯算法本身超出本书范围"
  ],
  "canonical_terms": {
    "深度优先搜索（DFS）": "一条路走到底再回退的图遍历策略",
    "访问标记（Visited）": "记录顶点是否访问过，防止在有环图中无限循环",
    "回溯（Backtracking）": "尝试后如果失败就撤销选择"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数"
  },
  "assumptions": [
    "读者已掌握 9.2 的树遍历与 12.1 的图表示",
    "读者理解 2.1 的去程/回程与 9.4 的回溯"
  ],
  "word_count_actual": 3120,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch12/Sec122/",
    "递归/迭代 DFS 顺序、不逆序的结果、三条路径、10 万顶点耗时均为实测",
    "练习 12.2.1 的 DFS 推演已手工验算（0→1→3→2→4）",
    "术语写法与 glossary.md 一致"
  ],
  "next": "12.3 广度优先搜索"
}