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)，线性边计数。