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

题目描述
给定一个有向图，判断其是否存在欧拉回路，若存在则找出该回路。欧拉回路要求经过图中每条边恰好一次，并最终回到起点。有向图存在欧拉回路的充要条件是：图是强连通的（除孤立点外），且每个顶点的入度等于出度。

解题步骤

1. 条件检查

   • 遍历所有顶点，检查每个顶点的入度是否等于出度。若存在任一顶点不满足，则无欧拉回路。
   • 检查图的基图（忽略边方向后的无向图）是否连通（通过DFS/BFS），确保非孤立点之间可达。若存在多个连通分量且均包含边，则无解。

2. Hierholzer算法核心过程

   • 步骤1：任选一个顶点（若为欧拉回路，起点可任意；若为欧拉路径，需选入度比出度少1的顶点作为起点）。
   • 步骤2：从起点开始进行深度优先遍历，每次选择一条未访问的边，直到无法继续（即当前顶点的出边已用完）。此时回溯路径形成一个临时环。
   • 步骤3：若临时环未覆盖所有边，则从当前环上找一个仍有未访问出边的顶点，以其为起点重复步骤2，生成新环，并将新环插入原环的对应位置。
   • 步骤4：重复步骤3直到所有边被纳入环中，最终环即为欧拉回路。

3. 算法优化实现

   • 使用栈（或递归）记录当前路径，利用哈希表或邻接表动态删除已访问边（避免重复访问）。
   • 时间复杂度：O(|E|)，其中|E|为边数。

举例说明
假设有向图如下（边按字母顺序标记）：
顶点：0, 1, 2
边：0→1 (a), 1→2 (b), 2→0 (c)

1. 检查条件：每个顶点入度=出度=1，且图连通，满足欧拉回路存在条件。
2. 从顶点0开始：
   • 走边a到顶点1，再走边b到顶点2，最后走边c回顶点0，形成环[0,1,2,0]。
   • 所有边已被访问，算法结束，欧拉回路为a→b→c。

关键点

• Hierholzer算法通过局部环的合并逐步构建全局回路，避免暴力搜索。
• 需注意有向图与无向图在度数和连通性判断上的差异。