網頁

2020/4/10

Floyd Cycle Detection Algorithm 龜兔賽跑算法

Floyd Cycle Detection Algorithm(Floyd判圈算法),又稱Tortoise and Hare Algorithm(龜兔賽跑算法),此演算法可用來判斷LinkedList(鏈接串列)或是否存在cycle(環),並找出環的起始節點及算出cycle的長度。

此算法找出串列是否有cycle存在的方法如下:

  1. 使用兩個pointer(指針)t及h指向串列的起點S。t代表烏龜(tortoise),h代表兔子(hare)。兩個指針同時向後移動,而h(兔子)移動的速度是t(烏龜)的兩倍,換句話說就是t每次移動1步(1個節點),h每次移動2步(2個節點)。
  2. 如果兩個指針t和h持續沿串列移動到最後沒有任何節點,代表此串列沒有cycle。
  3. 如果兩個指針t和h持續移動並在同個節點M相遇,代表此串列有cycle。

兩個指針t及h指向串列的起點S

兩個指針同時向後移動,而h(兔子)移動的速度是t(烏龜)的兩倍。

兩指針在同個節點M相遇表示串列存在cycle。


找出cycle起點及長度的方法如下:

  1. 當兩指針相遇後,把其中一個指針h重置到串列起點S,另一個指針t保持在之前兩指針相遇的節點M上。
  2. 接著兩指針同時開始向後移動,但此時兩指針移動的速度相同,每次都是往後1步,兩指針持續移動直到再次相遇的節點即為cycle的起始位置C。
  3. 保持一個指針h不動,另一個指針t每次移動1步直到兩指針再次相遇,則t的步數(經過的節點數)即為cycle的長度。

把h移至串列起點S,然後與停留在M的t同時以相同速度向後移動直到相遇的節點C即為cycle起始節點。

指針h不動,指針t每次移動1步再次遇見指針h,則t經過的節點數即為cycle的長度。


會寫這篇的原因是在Youtube看到Joma Tech - If Programming Was An Anime這部影片,蠻好笑的,然後對這算法也很好奇,上網了解後整理的結果。


沒有留言:

張貼留言