无向图的Hierholzer算法流程（一）

无向图的Hierholzer算法

细心的读者可能发现了上述分析中的一个漏洞：上述分析只能说明，当图中存在度数为奇数的节点时，不存在欧拉回路。我们还需要一个用来找出欧拉回路的算法，才能证明当所有节点度数为偶数时，欧拉回路确实存在。事实上，欧拉本人也没有完成这一证明，该证明的补全由德国数学家 Carl Hierholzer 于 1871 年完成[^3]。

算法流程

Hierholzer 的基本思想是首先找到一个子回路，并逐步将其他回路合并到该子回路中，最终形成完整的欧拉回路。该证明被后人整理成 Hierholzer 算法^4，用于在已经判定无向图的欧拉回路存在的前提下，找出一条欧拉回路。算法流程如下：

• （寻找子回路）从任意非零度节点 出发，沿着边遍历图。在遍历过程中，删除经过的边。如果遇到一个所有边都被删除的节点，那么该节点必然是 （证明见下文），即我们找到了一个包含 的回路。将该回路上的节点和边添加到结果序列中。
• （检查是否存在其它回路）检查刚刚添加到结果序列中的节点，看是否还有与节点相连，且未遍历的边。如果发现节点 有未遍历的边，则从 出发重复步骤 1，找到一个包含 的新回路，将结果序列中的一个 用这个新回路替换。此时结果序列仍然是一个回路，只不过变得更长了。
• （结束条件）重复步骤 2，直到所有边都被遍历。此时结果序列中的节点和边就构成了欧拉回路。算法结束。