algorithm - Fleury 算法的时间复杂度

Question

您能否帮我找出 Fleury 算法（用于获取欧拉回路）的时间复杂度？

Answer 1

在您指定如何识别桥边缘之前，Fleury 的算法并不是真正完整的。Tarjan 提供了一种用于识别所有桥梁的线性时间算法（请参阅http://en.wikipedia.org/wiki/Bridge_(graph_theory)），因此在每个删除的边之后重新运行 Tarjan 算法的简单实现将是 O(E^2 ）。可能有更好的方法来重新计算桥集，但也有更好的 O(E) 算法。（见http://www.algorithmist.com/index.php/Euler_tour#Fleury.27s_algorithm；不是我的网站:)）

Answer 2

在这里： http ://roticv.rantx.com/book/Eulerianpathandcircuit.pdf 您可以阅读除其他内容外，它是 O(E)，线性边数。

Answer 3

Fleury 算法涉及以下步骤：

1. 确保图形有 0 个或 2 个奇数顶点。

2. 如果有 0 个奇数顶点，则从任何地方开始。如果有 2 个奇数顶点，则从其中一个开始。

3. 一次跟随一个边缘。如果您在桥接和非桥接之间进行选择，请始终选择非桥接。

4. 当你用完边缘时停止。

如果通过 Tarjan 算法找到了桥，并且这些桥存储在邻接矩阵中，那么我们不需要每次都运行 tarjan 算法来检查一条边是否是桥。我们可以在 O(1) 时间内检查所有其他网桥查询。因此 Flury 的算法时间复杂度可以降低到 O(V+E) {因为这是一个 DFS}，但是这种方法需要 O(V2) 额外的空间来存储桥。