我成功地创建了一个算法，可以在时间复杂度为O(k^2 * n)的情况下找到一个无向连通图中的欧拉路径（如果存在）其中：
k: 边数 n: 节点数
我想知道是否有更好的算法，如果有，它的思路是什么。
谢谢！ :)
k: 边数 n: 节点数
我想知道是否有更好的算法，如果有，它的思路是什么。
谢谢！ :)
在无向图中寻找欧拉路径的最佳时间复杂度是多少？
3
- gdaras
2
3您可以使用Hierholzer算法达到O(k)的时间复杂度。 - Nico Schertler
谢谢你的回答 :) - gdaras
1个回答
5
Hierholzer算法的时间复杂度为O(k): https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm
首先，您需要找到两个度数为奇数的顶点之间的路径。然后，只要在路径上有未使用的边的顶点，就从该顶点沿着未使用的边继续前进，直到再次回到该顶点，然后合并新路径。
如果没有度数为奇数的顶点，则可以从任何顶点开始一个空路径。
如果度数为奇数的顶点数不是0或2，则不存在欧拉路径。
如果没有度数为奇数的顶点，则可以从任何顶点开始一个空路径。
如果度数为奇数的顶点数不是0或2，则不存在欧拉路径。
- Matt Timmermans
3
非常有帮助的答案。非常感谢 :) - gdaras
1从维基百科上看，Hierholzer算法计算的是欧拉回路，而不是欧拉路径。你能给我提供这个答案算法的引用吗？ - Bing Zhao
证明它有效很容易。如果你移除奇数顶点之间的初始路径，那么剩余图中的所有顶点都会具有偶数度数。你会在这个图的每个连通分量中找到欧拉回路，并将它们添加到初始路径中。 - Matt Timmermans
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接