跳转至

十二、深度优先搜索的应用

考点速览

# 考点 题型 重要度
1 DFS 模板与复杂度 填空 / 选择 ★★★
2 无向图列连通分量 简答 ★★
3 割点的两种判定（根 / 非根） 大题 ★★★★★
4 \(\text{Num}\) 与 \(\text{Low}\) 的求法 大题手算 ★★★★★
5 双连通分量的性质 填空 ★★★
6 欧拉回路 / 欧拉路径存在条件 选择 / 填空 ★★★★★
7 DFS 求欧拉回路的实现要点 简答 ★★★
8 哈密顿回路 vs 欧拉回路 选择 ★★★

DFS 是前序遍历（preorder traversal）的推广。

考点 1：DFS 模板（必背）

void DFS(Vertex V)  /* this is only a template */
{   visited[V] = true;  /* mark this vertex to avoid cycles */
    for (each W adjacent to V)
        if (!visited[W])
            DFS(W);
}  /* T = O(|E| + |V|) as long as adjacency lists are used */

时间复杂度（必考填空）：邻接表实现下 \(T = O(|E| + |V|)\)。

易错点

复杂度是 \(O(\|E\| + \|V\|)\)，不是 \(O(\|V\|^2)\)——后者是邻接矩阵下的复杂度。

考点 2：列连通分量

void ListComponents(Graph G)
{   for (each V in G)
        if (!visited[V]) {
            DFS(V);
            printf("\n");
        }
}

思路：外层循环找未访问的顶点，每次进入 DFS 即扩展出一个完整的连通分量。

双连通性（Biconnectivity）—— 本章核心大题

考点 5：基本概念（先背定义）

概念 定义
割点（Articulation Point） 删除该点后，\(G - v\) 至少分裂为 2 个连通分量
双连通图 连通且没有割点
双连通分量 极大双连通子图

重要性质（填空）

任何两个双连通分量不共享边 → \(E(G)\) 被双连通分量划分（partition）。

考点 3 + 4：找割点的 DFS 算法（手算大题）

Step 1：跑一遍 DFS 得到 DFS 生成树

编号规则：若 \(u\) 是 \(v\) 的祖先 → \(\text{Num}(u) < \text{Num}(v)\)（即按访问顺序编号）。

Step 2：递归求 \(\text{Low}\) 值

\[ Low(u) = \min \begin{cases} Num(u) \\ \min\{Low(w) \mid w \text{ 是 } u \text{ 的子节点}\} \\ \min\{Num(w) \mid (u, w) \text{ 是一条回边（back edge）}\} \end{cases} \]

口诀：自己的 Num，所有儿子的 Low，所有回边指向的 Num——三者取最小。

Step 3：套割点判定（两条独立规则）

情形 判定
\(u\) 是根 在 DFS 树中有 \(\geq 2\) 棵子树 → 割点
\(u\) 非根 存在子节点 \(\text{child}\) 使 \(\text{Low}(\text{child}) \geq \text{Num}(u)\) → 割点

解题答题模板（每次都这么写）

  1. 画出 DFS 生成树，标 \(\text{Num}\)；
  2. 后序回算每个点的 \(\text{Low}\)；
  3. 对每个点逐一套上面两条判定；
  4. 列出所有割点。

例题走查（PPT 给的 DFS(3) 数据）

vertex 0 1 2 3 4 5 6 7 8 9
Num 4 3 2 0 1 5 6 7 9 8
Low 4 0 0 0 0 5 5 5 9 8

怎么读这张表：

  • 顶点 3 是根（\(\text{Num}=0\)）。若它在 DFS 树中有 ≥ 2 子树 → 割点。
  • 顶点 5 非根，看它子节点的 \(\text{Low}\) 是否 \(\geq \text{Num}(5)=5\)；表中能看到 6、7 的 \(\text{Low}=5 \geq 5\) → 5 满足判定 → 割点。
  • 顶点 1（\(\text{Num}=3, \text{Low}=0\)）：它的子节点 \(\text{Low}\) 能跳到 0 < 3 → 不是割点。

易错点

  • \(\text{Low}\) 是后序算的，必须先算完所有子节点。
  • 回边只看 \(\text{Num}\)，不看 \(\text{Low}\)。
  • 判定式是 \(\geq\)，不是 \(>\)。

欧拉回路（Euler Circuits）

考点 6：定义与存在条件（必考）

概念 定义
欧拉路径（Euler Tour） 不提笔画完图中所有边恰好一次
欧拉回路（Euler Circuit） 不提笔画完所有边恰好一次，且回到起点

命题 1（欧拉回路）

存在 ⟺ 图连通 且 每个顶点度数都是偶数。

命题 2（欧拉路径）

存在 ⟺ 图恰好有两个奇度顶点；必须从其中一个奇度顶点出发。

易错点（高频选择题）

  • 「全偶」→ 有欧拉回路。
  • 「恰好 2 个奇」→ 只有欧拉路径，没有回路；起点必须是奇度点。
  • 奇度点个数若 \(\notin \{0, 2\}\) → 两者都没有。

考点 7：DFS 求欧拉回路的实现要点

  • 路径用链表（linked list）维护；
  • 每个邻接表维护一个指向最后扫描边的指针，避免重复扫描；
  • 时间复杂度：\(T = O(|E| + |V|)\)。

考点 8：哈密顿回路 vs 欧拉回路（对比题）

维度 欧拉回路 哈密顿回路
走过对象 每条边恰好一次 每个顶点恰好一次
判定难度 多项式（看度数） NP 完全（无已知多项式算法）
算法 DFS, \(O(\|E\| + \|V\|)\) 暂无高效算法

结论

考试如果问「以下哪个问题可以高效求解」——欧拉可以，哈密顿不行。