弗洛伊德的循環尋找算法 - 需要兩個指針？

Question

我今天正在通過Floyd的循環尋找算法，並且有疑問。爲什麼他需要兩個指針並以不同的速度移動它們？

他可以代替創建兩個指針保持一個靜態的，它的指針和其他指針，這是他比較遞增？我的意思是即使這樣也會導致查找週期正確嗎？

Answer 1

他們需要移動的原因是，循環不一定循環節點的完整列表。

例如，假設我們有4個節點A-> B-> C-> D->乙

如果我們保持一個指針指向A，我們從來沒有檢測週期。

Answer 2

的原因是，需要增加其後面的指針（上升更慢），把它弄出來的任何分支脫落的週期。

例如，邊A => B，B => C，C => A，D => B，E => D。

假設兩個指針都從E開始。那麼如果你不改變一個指針，去E => d => B => C => A => B => C => ...，並且永遠不會E.

當別人說你不會得到相同的算法的複雜性，他們意味着你將不得不嘗試從每個頂點開始（這是較慢的）。使用快/慢指針方法，您只需嘗試從圖ONCE的每個「組件」開始。一個組件是所有相互連接的頂點。分離的組件意味着頂點不通過邊緣連接。

通過增加緩慢指針，它也將進入A => B =>碳循環。

而且它絕不會錯過，因爲在指針的變化有效差只有1即。如果快速指針趕上慢速指針，它們之間的距離每次迭代只會改變1。所以，最終的距離將達到0.1