弗洛伊算法的时间复杂度

Question

请问能否帮我查找一下 Fleury 算法（用于获取欧拉回路）的时间复杂度？

- Kevin

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；这不是我的网站 :))。

- user287792

Answer 2

这里：http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf，你可以阅读到关于欧拉路径和欧拉回路的内容，其中提到时间复杂度为O(E)，即边数的线性。

- Gabriel Ščerbák

---

它将我第二个链接中的算法归因于Fleury，但我找不到任何其他支持此说法的来源。 - user287792

我不熟悉那个算法或那篇论文，所以我无法判断。 - Gabriel Ščerbák

Answer 3

Fleury算法包括以下步骤：

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

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

3. 逐个跟随边缘。如果在桥和非桥之间有选择，则始终选择非桥。

4. 当没有边可用时停止。

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

- Himanshu Singh