Fleury算法的時間複雜度

Question

您能否幫我找出Fleury算法（用於獲得歐拉電路）的時間複雜度？

Answer 1

這裏： http://roticv.rantx.com/book/Eulerianpathandcircuit.pdf 你可以讀取其他東西，它是O（E），線性邊數。

Answer 2

直到您指定如何識別網橋邊緣之後，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 3

弗勒算法包括以下步驟：

1. 確保有圖有0或2奇頂點。

2. 如果有0個奇數頂點，從任何地方開始。如果有2個奇數頂點，從其中一個頂點開始。

3. 沿着一條邊一次。如果您在橋樑和非橋樑之間進行選擇，請始終選擇非橋樑。

4. 當您用完邊緣時停止。

如果通過的Tarjan的算法發現橋樑出來，這些橋都存儲在一個鄰接矩陣然後我們不必每次檢查的邊緣是橋或沒有時間運行的Tarjan的算法。我們可以在O（1）時間檢查所有其他網橋查詢。因此Flury的算法時間複雜度可以降低到O（V + E）（因爲這是一個DFS），但是這種方法需要O（V2）額外的空間來存儲網橋。