欧拉回路与欧拉路径的算法流程演示

算法流程演示

算法流程可能有一些复杂，我们通过一个例子来理解算法的执行步骤。例如，考虑用 Hierholzer 算法找出下图的欧拉回路。

首先进行步骤 1 。从任意节点出发（不妨从节点 出发），沿着边遍历图，删除经过的边，直到无法继续前进。假设我们的遍历路径为 ，此时我们找到了一个包含 的回路。将该回路添加到结果序列中，此时的结果序列即为 ，而图也变成了下面的样子。

接下来进行步骤 2 。检查刚刚添加到结果序列中的节点（节点 、 、 ）。我们发现，节点 还存在未被遍历的边（ 和 ），因此我们从节点 出发，重复步骤 1。假设我们的遍历路径为 ，此时我们找到了一个包含 的回路。将结果序列中的一个 换成这个回路，此时的结果序列即为 ，而图也变成了下面的样子。

重复进行步骤 2 。检查刚刚添加到结果序列中的节点（节点 、、）。我们发现，节点 还存在未被遍历的边（ 和 ），因此我们从节点 出发，重复步骤 1。假设我们的遍历路径为 ，此时我们找到了一个包含 的回路。将结果序列中的一个 换成这个回路，此时的结果序列即为 ，而图也变成了下面的样子。

重复进行步骤 2。检查刚刚添加到结果序列中的节点（节点 、、）。此时不存在未遍历的边，因此结果序列 就是原图中的一个欧拉回路。算法结束。

正确性证明

我们通过反证法简要说明一下，为什么步骤 1 中，如果遇到一个节点 不存在未被删除的边（即节点 的度数为 ），那么该节点必然是出发点 。

首先，假设 ，那么在遍历过程中，为了最终进入节点 ，进入 的边数需要恰好比离开 的边数多 ，也就是说节点 的度数将减少一个奇数。

然而，由于原图存在欧拉回路，因此节点 的初始度数为偶数。偶数减去奇数不可能等于 ，因此必然有 。

至于为什么该算法可以遍历所有边，简单来说是因为所有非零度节点是连通的。详细的证明需要用到一个关于连通性的反证法，有兴趣的读者可以参考《Pearls in Graph Theory》一书中 3.1 节的相关证明[^5]。