xxx 欧拉回路的 Hierholzer 算法

题目描述

给定一个有向图或无向图，判断图中是否存在一条欧拉回路（Eulerian circuit）——即一条路径，从某个顶点出发，恰好经过每条边一次，最终回到起点。如果存在，请输出该回路的具体路径。

约束条件：

• 图可能包含平行边（多重边）或自环。
• 要求算法的时间复杂度为 O(E)，其中 E 是边的数量。
• 图以邻接表形式给出。

背景知识

欧拉回路的存在性判定由欧拉在 1736 年解决，称为欧拉定理：

1. 无向图存在欧拉回路的充要条件：

   • 图是连通的（忽略孤立点）。
   • 每个顶点的度数（相邻边的数量）都是偶数。

2. 有向图存在欧拉回路的充要条件：

   • 图是弱连通的（忽略边的方向后连通）。
   • 每个顶点的入度等于出度。

如果条件满足，我们可以使用 Hierholzer 算法高效地构造出欧拉回路。

解题步骤

步骤 1：检查欧拉回路的存在性

在构造回路前，必须先验证图是否满足上述条件。

具体操作：

1. 确定图的类型（有向/无向）。
2. 检查图的连通性：
   • 对于无向图：从任意有边的顶点开始 DFS/BFS，检查是否所有有边的顶点都被访问到。
   • 对于有向图：忽略方向后做连通性检查（弱连通）。
3. 检查度数条件：
   • 无向图：统计每个顶点的度数，必须全为偶数。
   • 有向图：统计每个顶点的入度和出度，必须全部相等。

如果条件不满足，则直接输出“不存在欧拉回路”。

步骤 2：Hierholzer 算法的核心思想

Hierholzer 算法是一种 DFS 的变体，通过“拆边遍历”和“回溯拼接”来构造回路。
它的基本流程如下：

1. 从任意符合条件的顶点（对于无向图，任意度数非零的顶点；对于有向图，任意出度非零的顶点）开始，进行深度优先遍历。
2. 每走过一条边，就将其从图中“删除”（或标记为已访问），确保每条边只走一次。
3. 当当前顶点没有未访问的边时，将其加入回路路径。
4. 回溯到上一个顶点，继续尝试走未访问的边，并将新发现的环插入到回路路径的合适位置。
5. 最终，当所有边都被访问后，得到的逆序路径就是欧拉回路。

步骤 3：算法详细过程

我们以无向图为例，说明具体步骤：

输入：
顶点：0, 1, 2, 3
边：(0,1), (0,2), (1,2), (2,3), (2,3)（注意平行边）
邻接表表示：

0: [1, 2]
1: [0, 2]
2: [0, 1, 3, 3]
3: [2, 2]

检查条件：图连通，所有顶点度数均为偶数（0:2, 1:2, 2:4, 3:2），存在欧拉回路。

算法执行：

1. 选择起点 0，开始 DFS：

   • 从 0 走到 1（删除边 0-1）。
   • 从 1 走到 2（删除边 1-2）。
   • 从 2 走到 3（删除一条边 2-3）。
   • 从 3 走回 2（删除另一条边 3-2）。
   • 此时 2 还有未访问边：2-0。
   • 从 2 走到 0（删除边 2-0）。
   • 现在 0 没有未访问边，将 0 加入路径。

2. 回溯并拼接：

   • 回溯到 2，发现 2 已无未访问边，将 2 加入路径。
   • 回溯到 3，3 无边，将 3 加入路径。
   • 回溯到 2（第一次到达 2 时），2 已处理完，将 2 加入路径（注意：2 会多次加入，对应不同时间点）。
   • 回溯到 1，1 无边，将 1 加入路径。
   • 回溯到 0，0 已处理完，将 0 加入路径。

3. 最终路径（逆序记录）：[0, 1, 2, 3, 2, 0]
   反转后得到欧拉回路：[0, 2, 3, 2, 1, 0]。

注意：实际实现时，我们直接在 DFS 递归返回时将顶点加入栈，最后反转栈即可得到正确顺序。

步骤 4：算法实现细节

为了高效删除边，可以使用邻接表 + 指针或迭代器来标记已访问的边，避免每次从头遍历邻接表。

伪代码（无向图）：

Hierholzer(start):
    stack = []
    circuit = []
    stack.push(start)
    while stack not empty:
        v = stack.top()
        if adjacency_list[v] not empty:
            u = adjacency_list[v].pop_front()  // 删除边 v-u
            remove_edge(u, v)  // 同时删除无向边 u-v
            stack.push(u)
        else:
            circuit.push_back(v)
            stack.pop()
    reverse(circuit)  // 得到欧拉回路顺序
    return circuit

对于有向图，只需删除从 v 到 u 的边，无需对称删除。

步骤 5：时间复杂度分析

• 每条边只会被访问和删除一次。
• 删除操作在邻接表中可优化为 O(1)（使用链表迭代器或弹出末尾）。
• 总时间复杂度：O(E)，满足题目要求。

步骤 6：例题验证

用上述例子验证算法：

1. 检查条件通过。
2. 运行 Hierholzer 算法，得到回路 [0, 2, 3, 2, 1, 0]。
3. 验证：每条边恰好使用一次，起点终点相同，符合欧拉回路定义。

总结

Hierholzer 算法是构造欧拉回路的标准线性时间算法，核心在于递归删除边 + 回溯时记录顶点。
关键步骤：

1. 先判断存在性（连通性 + 度数条件）。
2. 从合适起点开始 DFS，边走边删边。
3. 在递归返回时将顶点加入路径，最后反转得到回路。

该算法同样适用于欧拉路径（起点终点不同）的情况，只需选择奇度顶点（无向图）或入度比出度大 1 的顶点（有向图）作为起点即可。