有向图中的欧拉回路存在性判定与 Hierholzer 算法 题目描述 给定一个 有向图 ，图中可能存在平行边（即两点间有多条方向相同的边）但无自环。请判断该图中是否存在 欧拉回路 ，如果存在，则找出该回路。 欧拉回路 的定义是：一条从某个顶点出发，沿着有向边的方向， 经过图中每条边恰好一次 ，最终回到起点的路径。 解题思路 解决此问题可分为两步： 存在性判定 ：依据图论中的定理，判断图中是否存在欧拉回路。 寻找回路 ：若存在，则使用高效的 Hierholzer 算法构造回路。 第一步：存在性判定 有向图中存在欧拉回路的 充要条件 是： 条件1 ：图是 强连通 的（从任意顶点出发都能到达其他所有顶点）。 条件2 ：每个顶点的 入度等于出度 （即 indegree(v) = outdegree(v) ）。 为什么需要强连通性？ 假设某个顶点入度等于出度，但图分成两个互不连通的部分，则无法从一部分走到另一部分并返回起点，无法形成全局回路。 如何检查强连通性？ 从任意顶点（例如顶点0）出发做一次DFS或BFS，检查是否能到达所有顶点。 将图中所有边反向，再从同一个顶点出发做一次DFS/BFS，检查是否能到达所有顶点。 若两次均能访问所有顶点，则图为强连通。 如何检查入度出度相等？ 遍历所有顶点，比较每个顶点的入边数和出边数即可。 第二步：Hierholzer 算法（寻找回路） 若满足存在性条件，可以使用 Hierholzer 算法 在线性时间内找出欧拉回路。该算法的核心是“拆圈合并”： 从任意顶点开始，进行 深度优先遍历 ，每次沿未访问的边移动，直到无法再移动（即当前顶点的所有出边均已访问），此时形成一个“小环”。 回溯时，若发现某个顶点还有未访问的出边，则从该顶点开始新的深度遍历，形成另一个小环，并将其插入到之前找到的路径中。 最终所有边都被访问，并形成完整回路。 具体步骤 ： 使用一个栈（或递归）来记录路径。 从起点出发，对每个顶点维护其“下一个要访问的出边”的索引（例如邻接表下标），避免重复检查已访问的边。 当某顶点的所有出边均被访问时，将该顶点加入路径（即回溯时记录）。 最终记录的路径是 逆序 的，反转后即为欧拉回路。 举例说明 假设有向图如下（顶点：0, 1, 2）： 边：0→1, 1→2, 2→0（这是一个有向三角形）。 步骤1：检查条件 每个顶点入度 = 出度 = 1。 从0出发可到达所有顶点；反向图从0出发也可到达所有顶点 → 强连通。 ⇒ 存在欧拉回路。 步骤2：Hierholzer 算法执行 从顶点0开始，边未访问状态： 0→1, 1→2, 2→0 。 从0出发，走 0→1 ，标记为已访问，当前路径记录为空，递归进入顶点1。 在顶点1，走 1→2 ，进入顶点2。 在顶点2，走 2→0 ，回到顶点0。 在顶点0，无未访问出边，将0加入路径（路径 = [ 0 ]），回溯到顶点2。 在顶点2，无未访问出边，将2加入路径（路径 = [ 0, 2 ]），回溯到顶点1。 在顶点1，无未访问出边，将1加入路径（路径 = [ 0, 2, 1 ]），回溯到顶点0。 递归结束，得到逆序路径 [ 0, 2, 1]，反转后为 [ 1, 2, 0]。但注意：这是顶点访问顺序，实际回路是边顺序 0→1, 1→2, 2→0 ，对应顶点序列 [ 0,1,2,0 ]。 在实现中，我们通常直接记录顶点序列，最终序列应为 [ 0,1,2,0 ]。 算法复杂度 存在性判定：强连通性检查（两次DFS/BFS）O(V+E)，入度出度检查 O(V)。 Hierholzer 算法：每个边访问一次，O(E)。 总复杂度为 O(V+E) ，线性时间。 关键点总结 有向图欧拉回路存在的 充要条件 是：强连通 + 每个顶点入度=出度。 Hierholzer 算法通过“深度遍历 + 回溯时记录顶点”高效构造回路，避免指数级搜索。 该算法可处理平行边，只要在访问时标记每条边即可。 通过以上步骤，你可以在线性时间内判断并找到有向图的欧拉回路。