在无向图中查找欧拉路径的最佳时间复杂度

Question

我设法创建了一种算法，可以在时间复杂度为 O(k^2 * n) 的无向连通图中找到欧拉路径（如果有的话），其中：

k：边数

n：节点数

我想知道是否有更好的算法，如果有的话，其背后的想法。

提前致谢！:)

Answer 1

Hierholzer 的算法运行时间为 O(k)： https: //en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm

首先，您找到两个具有奇数度的顶点之间的路径。然后，只要路径上有一个带有未使用边的顶点，就从该顶点开始跟踪未使用的边，直到再次回到该顶点，然后合并到新路径中。

如果没有奇数度数的顶点，那么您可以在任何顶点从空路径开始。

如果奇数度的顶点数不为 0 或 2，则不存在欧拉路径。