Hierholzer 算法寻找欧拉路径
原创约 2959 字
一句话总结
Hierholzer 算法是用于计算欧拉路径/欧拉回路的算法，其本质就是 遍历图结构所有边的 DFS 算法 的逆后序遍历结果。
在 欧拉图及一笔画游戏 中，我们通过经典的一笔画游戏学习了欧拉图的基本概念，探讨了欧拉路径/欧拉回路的判定条件。
关键就是看节点的度数，这里简单总结一下。如果你忘记了其中的原理，请先回去复习。
对于无向图：
如果所有节点的度数都是偶数，那么起点和终点是同一个节点，存在欧拉回路。我们可以以任意一个节点作为起点，遍历所有边后，一定可以回到起点。
如果存在两个奇数度节点，那么起点和终点分别是这两个节点，存在欧拉路径。我们可以任选一个奇数度节点作为起点，遍历所有边后，一定可以到达另一个奇数度节点。
对于有向图：
如果所有节点的入度和出度都相等，那么起点和终点是同一个节点，存在欧拉回路。我们可以以任意一个节点作为起点，遍历所有边后，一定可以回到起点。
如果存在两个节点入度和出度不相等，那么起点和终点分别是这两个节点，存在欧拉路径。我们可以任选一个入度和出度不相等的节点作为起点，遍历所有边后，一定可以到达另一个入度和出度不相等的节点。
接下来看看 Hierholzer 算法的代码实现，在 时间复杂度内找到欧拉路径/欧拉回路。