有向图中的欧拉回路（Hierholzer算法）

问题描述
给定一个有向图，判断是否存在欧拉回路，如果存在则找出该回路。欧拉回路是指一条经过图中每条边恰好一次且起点和终点相同的路径。

基本概念

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

   • 图是强连通的（不考虑孤立顶点）
   • 每个顶点的入度等于出度

2. 算法核心思想：

   • 从任意顶点开始进行深度优先遍历
   • 在回溯过程中将顶点加入回路
   • 利用栈来管理未完成的路径

算法步骤详解

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

1. 检查图的连通性：

   • 忽略孤立顶点（度为0的顶点）
   • 确保剩余顶点构成的子图是弱连通的

2. 检查度数条件：

   • 对每个顶点v，满足in_degree(v) = out_degree(v)
   • 如果存在不满足条件的顶点，则无欧拉回路

步骤2：初始化数据结构

1. 创建邻接表表示图
2. 维护每个顶点的当前出边索引
3. 初始化栈和结果路径：
   • 栈：存储待处理的顶点
   • 路径：存储最终的欧拉回路

步骤3：Hierholzer算法核心过程

1. 选择起始顶点：

   • 从任意非孤立顶点开始（通常选择第一个有边的顶点）
   • 将起始顶点压入栈

2. 深度优先遍历：

   • 当栈非空时：
     a. 取栈顶顶点u
     b. 如果u还有未访问的出边：
     • 通过当前出边索引获取下一条边(u, v)
     • 更新u的出边索引
     • 将v压入栈
       c. 如果u没有未访问的出边：
     • 将u弹出栈并加入路径

步骤4：路径反转
由于算法得到的是逆序的欧拉回路，需要将路径反转得到正确顺序。

具体示例
考虑有向图：顶点{0,1,2,3}，边：0→1, 1→2, 2→0, 1→3, 3→1

执行过程：

1. 检查条件：

   • 所有顶点入度=出度=2
   • 图是强连通的
   • 存在欧拉回路

2. 算法执行：

   • 从顶点0开始
   • 栈变化：[0] → [0,1] → [0,1,2] → [0,1] → [0,1,3] → [0,1] → [0] → []
   • 路径构建：2 → 3 → 1 → 0
   • 反转后：0→1→3→1→2→0

复杂度分析

• 时间复杂度：O(E)，其中E是边数
• 空间复杂度：O(V+E)，用于存储图结构和栈

关键要点

1. 算法确保每条边只被访问一次
2. 使用当前出边索引避免重复访问
3. 回溯时顶点加入路径保证回路完整性
4. 结果需要反转得到正确顺序

应用场景

• DNA测序
• 邮递员问题
• 网络路由优化
• 电路板布线