CS Wiki

20.3 深度优先搜索

43分钟阅读

相关笔记

概览

本节介绍 深度优先搜索（Depth-First Search, DFS）算法，它与 BFS 一样是图算法中最基础、最重要的搜索策略。DFS 采用纵深优先的策略：从源顶点出发，沿着一条路径尽可能深入探索，直到无法继续时回溯到上一个分叉点，再选择另一条路径继续深入。DFS 使用递归（或显式栈）实现，通过发现时间 和完成时间 两个时间戳记录每个顶点的探索过程。DFS 的核心成果包括：括号定理（描述顶点间的嵌套关系）、边分类（树边、后向边、前向边、横边）、白色路径定理（描述 DFS 树的构成）。DFS 是许多高级图算法的基础：拓扑排序、强连通分量、环检测等。DFS 的运行时间为 。

核心要点：

  • DFS 使用递归（或栈）实现纵深探索，时间复杂度
  • 每个顶点有发现时间 和完成时间 ，满足括号结构（嵌套或不相交）
  • 有向图的边分为四类：树边、后向边、前向边、横边
  • 无向图只有树边和后向边两类
  • 后向边标志着图中存在环
  • DFS 是拓扑排序和强连通分量算法的基础

知识结构总览

flowchart TD
    A["20.3 深度优先搜索 (DFS)"] --> B["算法流程"]
    A --> C["时间戳与括号定理"]
    A --> D["边分类"]
    A --> E["核心定理"]
    A --> F["复杂度与应用"]

    B --> B1["DFS(G): 全局初始化"]
    B --> B2["DFS-VISIT(G, u): 递归探索"]
    B --> B3["递归栈隐式管理回溯"]

    C --> C1["发现时间 d[u]"]
    C --> C2["完成时间 f[u]"]
    C --> C3["括号定理 (定理22.7)"]
    C --> C4["时间戳区间嵌套/不相交"]

    D --> D1["树边 (Tree Edge)"]
    D --> D2["后向边 (Back Edge)"]
    D --> D3["前向边 (Forward Edge)"]
    D --> D4["横边 (Cross Edge)"]
    D --> D5["无向图: 只有树边和后向边"]

    E --> E1["白色路径定理 (定理22.9)"]
    E --> E2["定理22.10: 无向图边分类"]

    F --> F1["拓扑排序"]
    F --> F2["强连通分量 (SCC)"]
    F --> F3["环检测"]
    F --> F4["迭代DFS (栈实现)"]

    style A fill:#4a90d9,color:#fff
    style C3 fill:#e74c3c,color:#fff
    style E1 fill:#27ae60,color:#fff
    style E2 fill:#27ae60,color:#fff

核心思想

核心思想

DFS 的核心策略是纵深优先：选择一条路径尽可能深入，走到尽头后回溯。这种策略天然适合用递归实现——递归调用栈自动管理”深入”和”回溯”的过程。DFS 为每个顶点记录两个时间戳：发现时间 （第一次访问 的时间）和完成时间 （完成对 所有邻居的探索的时间）。这两个时间戳蕴含了丰富的结构信息：顶点间的祖先-后代关系对应时间戳区间的嵌套关系，边类型可以由时间戳完全确定。

DFS 算法

算法执行流程

  1. 初始化所有顶点为白色（未访问），前驱为 NIL，时间戳 time=0
  2. 对每个白色顶点 u 调用 DFS-VISIT(G, u)
  3. DFS-VISIT：time 加 1，记录发现时间 d[u]，标记 u 为灰色（正在探索）
  4. 遍历 u 的每个白色邻居 v：设置 v 的前驱为 u，递归调用 DFS-VISIT(G, v)
  5. 所有邻居处理完毕后，标记 u 为黑色（探索完成），time 加 1，记录完成时间 f[u]
flowchart TD
    A["开始：输入图 G"] --> B["初始化所有顶点为白色<br/>time = 0"]
    B --> C{"还有白色顶点?"}
    C -- 是 --> D["取白色顶点 u<br/>调用 DFS-VISIT(G, u)"]
    D --> E["time++, u.d = time<br/>u.color = GRAY"]
    E --> F["遍历 u 的每个邻接顶点 v"]
    F --> G{"v.color == WHITE?"}
    G -- 是 --> H["v.pi = u<br/>DFS-VISIT(G, v)"]
    H --> I{"还有未检查的邻居?"}
    G -- 否 --> I
    I -- 是 --> F
    I -- 否 --> J["u.color = BLACK<br/>time++, u.f = time"]
    J --> C
    C -- 否 --> K["结束：所有顶点已访问"]

DFS(G)
1  for each vertex u ∈ G.V
2      u.color = WHITE
3      u.π = NIL
4  time = 0
5  for each vertex u ∈ G.V
6      if u.color == WHITE
7          DFS-VISIT(G, u)

DFS-VISIT(G, u)
1  time = time + 1
2  u.d = time
3  u.color = GRAY
4  for each v ∈ G.Adj[u]
5      if v.color == WHITE
6          v.π = u
7          DFS-VISIT(G, v)
8  u.color = BLACK
9  time = time + 1
10 u.f = time

顶点属性

DFS 顶点属性

DFS 为每个顶点 维护四个属性：

  • ：顶点颜色，取值为 WHITE（未发现）、GRAY（已发现，正在探索子树）、BLACK（探索完毕）
  • ：发现时间（discovery time），第一次访问 的时间戳
  • ：完成时间（finishing time），完成对 的所有可达顶点的探索的时间戳
  • ：DFS 树中 的前驱（父节点）

DFS 的执行过程

DFS 的执行过程分为两个阶段：

  1. 全局初始化（DFS 第 1-4 行）： 将所有顶点标记为 WHITE，前驱设为 NIL，全局时间计数器设为 0。

  2. 逐顶点探索（DFS 第 5-7 行）： 遍历所有顶点，对每个 WHITE 顶点调用 DFS-VISIT。这确保了即使图不连通，所有顶点都会被访问。

  3. 递归探索（DFS-VISIT）：

    • 记录发现时间 ，将 标记为 GRAY
    • 遍历 的所有邻居 ：如果 为 WHITE，递归调用 DFS-VISIT(G, v)
    • 所有邻居处理完毕后，将 标记为 BLACK，记录完成时间

括号定理

定理 22.7（括号定理）

在任何 DFS 中，对于任意两个顶点 和 ，以下三种情况恰好有一种成立：

  1. 区间 与 完全不相交： 和 之间没有祖先-后代关系，它们在不同的 DFS 树中，或在同一棵树中但一个是另一个的叔叔/侄子
  2. 区间 完全包含 ： 是 的真祖先（proper ancestor），即 在 的子树中
  3. 区间 完全包含 ： 是 的真祖先（proper ancestor）

边分类

DFS 边分类（有向图）

在 DFS 过程中，图的每条边 根据探索时的颜色被分为四类：

类型颜色条件含义
树边（Tree Edge） 为 WHITE 第一次被发现， 成为 DFS 树的一条边
后向边（Back Edge） 为 GRAY 是 的祖先， 指向已探索但未完成的祖先
前向边（Forward Edge） 为 BLACK， 是 的后代， 跳过中间节点直接指向后代
横边（Cross Edge） 为 BLACK， 与 没有祖先-后代关系， 跨越不同子树

边分类的判定在 DFS-VISIT 的第 5 行自然完成：

  • WHITE → 树边
  • GRAY → 后向边
  • BLACK → 前向边或横边（通过比较 值区分）

定理 22.10（无向图的边分类）

在对无向图 执行 DFS 时，每条边要么是树边，要么是后向边。无向图中不存在前向边和横边。

白色路径定理

定理 22.9（白色路径定理）

在 DFS 中，顶点 成为顶点 的后代，当且仅当在发现 的时刻 ，存在一条从 到 的全白色路径（即路径上所有顶点都是 WHITE）。

时间戳与边分类的关系

边分类的时间戳判定（习题 22.3-5）

对于有向图的 DFS，边 的类型可以通过时间戳判定：

类型时间戳条件
树边 且 （即 是 的后代）
后向边 且 （即 是 的祖先）
前向边 且 （ 是 的后代，但不是直接子节点）
横边 且 （ 与 无祖先-后代关系）

注意： 树边和前向边的时间戳条件形式上相同（ 且 ），区分方法是：树边是 DFS-VISIT 中递归调用产生的边，前向边是跳过中间节点的非树边。

复杂度分析

DFS 时间复杂度

邻接表表示：

  • 初始化（DFS 第 1-4 行）：
  • DFS-VISIT 调用：每个顶点恰好调用一次，每次调用中第 1-3 行和第 8-10 行共
  • 遍历邻接表：每条边被检查一次（有向图）或两次（无向图），
  • 总计：

邻接矩阵表示：

  • 每个顶点的邻居遍历需要扫描矩阵的一整行，
  • 共 个顶点，总计

补充理解与拓展

DFS 的发明历史

DFS 的形式化描述归功于 Robert Tarjan（1972）：

  • Robert Tarjan（1972）：在论文 “Depth-first search and linear graph algorithms”（SIAM Journal on Computing, 1(2):146-160）中首次系统阐述了 DFS 的理论框架，包括时间戳、边分类、DFS 树等概念，并展示了如何用 DFS 在线性时间内解决连通分量、拓扑排序、强连通分量等问题。这篇论文是图算法领域的里程碑之作。

DFS 的思想实际上可以追溯到更早：

  • Trémaux（19 世纪）：提出了一种用 DFS 思想走迷宫的方法（用粉笔标记已访问的路口）
  • Tarjan 的工作将这一直觉上升为严格的算法框架，并证明了其在线性时间内的正确性

Tarjan 因此获得了 1986 年的图灵奖（部分原因）。DFS 至今仍是图算法中最核心的工具。

来源：Tarjan, R.E., “Depth-first search and linear graph algorithms”, SIAM J. Comput., 1972

DFS 的实际应用

DFS 在计算机科学的各个领域都有广泛应用：

  1. 编译器设计：语法分析（递归下降分析器本质上是 DFS），检测递归类型定义中的循环引用

  2. 环检测：后向边的存在等价于图中存在有向环。DFS 是检测环的标准方法，时间 。应用于死锁检测（资源分配图中检测环）

  3. 拓扑排序：对 DAG（有向无环图）按完成时间 的逆序排列，得到拓扑序。应用于任务调度、编译依赖分析、课程先修关系

  4. 强连通分量（SCC）：Kosaraju 算法和 Tarjan SCC 算法都基于 DFS。应用于网页分析（同一网站的页面构成 SCC）、社交网络社区发现

  5. 迷宫生成：DFS 随机选择邻居生成完美迷宫（每对格子之间恰好有一条路径），这是最常见的迷宫生成算法

  6. 2-SAT 求解：通过构建蕴含图并用 DFS 求强连通分量来判定 2-SAT 的可满足性

来源：Tarjan, 1972; Cormen et al., CLRS Chapter 22; Aho et al., “Compilers”, 2006

迭代 DFS（习题 22.3-7）

递归 DFS 在深度很大的图上可能导致栈溢出（stack overflow）。解决方案是使用显式栈模拟递归：

ITERATIVE-DFS(G)
1  for each vertex u ∈ G.V
2      u.color = WHITE
3      u.π = NIL
4  time = 0
5  for each vertex u ∈ G.V
6      if u.color == WHITE
7          ITERATIVE-DFS-VISIT(G, u)

ITERATIVE-DFS-VISIT(G, s)
1  S = 空栈
2  PUSH(S, (s, false))  // (顶点, 是否已处理邻居)
3  while S ≠ ∅
4      (u, processed) = POP(S)
5      if processed
6          u.color = BLACK
7          time = time + 1
8          u.f = time
9      else if u.color == WHITE
10         time = time + 1
11         u.d = time
12         u.color = GRAY
13         PUSH(S, (u, true))  // 延后处理完成
14         for each v ∈ G.Adj[u]  // 逆序入栈以保持顺序一致
15             if v.color == WHITE
16                 v.π = u
17                 PUSH(S, (v, false))

关键技巧： 每个顶点入栈两次——第一次是”发现”（设置 ，标记 GRAY），第二次是”完成”（设置 ，标记 BLACK）。第二次出栈时 processed == true，执行完成操作。这精确模拟了递归 DFS 的行为。

注意： 第 14 行中邻居需要逆序入栈，才能保持与递归 DFS 相同的访问顺序（因为栈是 LIFO）。

空间： 显式栈的最大深度为 ，与递归栈相同。但在某些语言/环境中，显式栈可以分配在堆上，避免系统栈溢出。

边分类的直觉理解

DFS 的四种边类型可以用”家谱”类比来理解：

  • 树边：父→子的关系，就像族谱中的父子关系
  • 后向边：子→祖先的关系，就像”回老家”——你指向你的祖父
  • 前向边：祖先→非直接后代，就像祖父直接联系孙子，跳过了父亲
  • 横边：堂兄弟之间的关系，两个顶点没有祖先-后代关系

后向边的重要性： 后向边是唯一标志着有向环存在的边类型。如果有向图中存在后向边，则图中存在有向环；如果不存在后向边，则图是 DAG（有向无环图）。这一性质是拓扑排序和 DAG 相关算法的理论基础。

易混淆点与辨析

DFS 的时间戳不唯一

❌ 常见错误：认为 DFS 产生唯一的时间戳序列。

✅ 正确理解：DFS 的时间戳取决于邻接表中邻居的排列顺序和主循环中顶点的遍历顺序。不同的顺序产生不同的 DFS 森林和不同的时间戳。但无论哪种 DFS，括号定理、边分类规则和白色路径定理始终成立。

前向边与树边的时间戳条件相同

❌ 常见错误：认为前向边和树边可以通过时间戳完全区分。

✅ 正确理解：树边和前向边的时间戳条件形式上相同（ 且 ）。区分方法是：树边是在 DFS-VISIT 中通过递归调用产生的（ 为 WHITE），前向边是 已经为 BLACK 时发现的（ 是 的后代但不是通过当前递归路径到达的）。因此，边分类需要在 DFS 执行过程中根据颜色判定，而非事后仅凭时间戳。

无向图的"后向边"不是真正的环

❌ 常见错误：认为无向图中存在后向边意味着图中存在环。

✅ 正确理解：在无向图的 DFS 中，每条非树边都被归类为”后向边”，但这是因为在无向图中，从子节点检查父节点时父节点一定是 GRAY。这种”后向边”实际上只是树边的反向遍历，不代表真正的环。只有当无向图中存在一条连接两个不同祖先-后代关系顶点的非树边时，才形成真正的环。

精确判断无向图是否有环： 如果无向图中存在一条非树边 ，且 不是 的父节点（），则图中存在环。

DFS 不计算最短路径

❌ 常见错误：认为 DFS 可以找到最短路径。

✅ 正确理解：DFS 找到的路径不保证是最短的。DFS 的纵深策略可能导致它找到一条很长的路径到达目标，而忽略了更短的路径。寻找最短路径应使用 BFS（无权图）或 Dijkstra 算法（非负权图）。

反例： 在图 和 中，DFS 可能先探索 ，找到长度为 4 的路径，而最短路径 长度仅为 1。

习题精选

题号题目描述难度
22.3-1颜色-边类型矩阵：在 DFS 中，根据 的颜色判断边 的类型★★☆
22.3-2给定图，展示 DFS 的完整执行过程（d, f, π 值）★★☆
22.3-3展示 DFS 执行过程的括号结构★★☆
22.3-5用时间戳条件判定边类型★★★
22.3-7给出迭代版本的 DFS★★★
22.3-8举反例说明 DFS 不保证找到最短路径★☆☆
22.3-9举反例说明 DFS 树不唯一★☆☆
22.3-10修改 DFS 打印每条边的类型★★☆
22.3-12修改 DFS 计算连通分量★★☆
22.3-13判断有向图是否是单连通的★★★

视频学习指南

资源主题链接说明
MIT 6.006 Lecture 14Depth-First Searchhttps://www.youtube.com/watch?v=AfSk24UTFS8Erik Demaine 教授，完整讲解 DFS 算法与括号定理
MIT 6.006 Lecture 15 (cont.)DFS Edge Classificationhttps://www.youtube.com/watch?v=wUgWX0nc4OM边分类、拓扑排序、SCC 的引入
Abdul BariDFS Algorithmhttps://www.youtube.com/watch?v=pcKY4hjDr6k逐步动画演示 DFS 执行过程
WilliamFisetDFS Graph Algorithmhttps://www.youtube.com/watch?v=7fujbpJ0LB4数据结构系列，含代码实现
NeetCodeDFS Introductionhttps://www.youtube.com/watch?v=Bt3F2rO1bQILeetCode 刷题视角，含经典 DFS 题目分类
3Blue1BrownGraph Algorithmshttps://www.youtube.com/watch?v=09_LlHjoEiY可视化 DFS，直观理解回溯过程

教材原文

原文摘录（CLRS 第4版 22.3节）

The strategy adopted by depth-first search is, as its name implies, to search “deeper” in the graph whenever possible. Depth-first search explores edges out of the most recently discovered vertex that still has unexplored edges leaving it. Once all of ‘s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which was discovered.

深度优先搜索所采用的策略，顾名思义，就是尽可能深地搜索图。深度优先搜索从最近发现的、仍有未探索出边的顶点 出发探索边。一旦 的所有边都被探索完毕，搜索就”回溯”到发现 的那个顶点，从那里继续探索。

原文摘录（CLRS 第4版 22.3节）

The procedure DFS records, for each vertex , a discovery time and a finishing time . These times are integers between 1 and , and the discovery time precedes the finishing time. The timestamps provide important information about the structure of the DFS forest.

过程 DFS 为每个顶点 记录一个发现时间 和一个完成时间 。这些时间是 1 到 之间的整数，且发现时间先于完成时间。时间戳提供了关于 DFS 森林结构的重要信息。

原文摘录（CLRS 第4版 22.3节，定理 22.7）

Theorem 22.7 (Parenthesis theorem) In any depth-first search of a (directed or undirected) graph , for any two vertices and , exactly one of the following three conditions holds: the intervals and are entirely disjoint, the interval is contained entirely within the interval , or the interval is contained entirely within the interval .

定理 22.7（括号定理） 在对（有向或无向）图 的任何深度优先搜索中，对于任意两个顶点 和 ，以下三种条件恰好有一种成立：区间 和 完全不相交，区间 完全包含在 中，或区间 完全包含在 中。

原文摘录（CLRS 第4版 22.3节，定理 22.9）

Theorem 22.9 (White-path theorem) In a depth-first forest of a graph , vertex is a descendant of vertex if and only if at the time that the search discovers , there is a path from to consisting entirely of white vertices.

定理 22.9（白色路径定理） 在图 的深度优先森林中，顶点 是顶点 的后代，当且仅当在搜索发现 的时刻 ，存在一条从 到 的完全由白色顶点组成的路径。

参见Wiki

第20章-基本图算法 深度优先搜索

关系图谱

反向链接