# 探索 Floyd Cycle Detection Algorithm

當你想解決任何一個需要檢測在多個相互連接的元素是否著環狀結構之場景，比如說

1. 道路模型。
2. 由多個有限狀態所組成的數學模型。
3. 有限輸入下在同一個函式f(x)所形成的結果，比如集合為{1,2}，且f(1)=2以及f(2)=1，在這裏1和2就透過函式關係形成一個環狀結構。

你會怎麼檢測它？放棄它，反正以後碰不上？
當然我會建議不放棄它，畢竟你不能夠確定在未來路上不會遇上類似的問題。那麼正式進入正題，如果肯冷靜思考的話，其實不論哪一個場景，都可以將這些場景轉化成由多個節點所組成的結構：


或者


當我們轉換成如此的結構時，我們可以更容易以肉眼看出哪些模型存在著循環，在這裏我們可以知道隊列A就是存在著循環，而隊列B由於尾巴部分並未跟前幾個節點相接，所以不構成循環。在這裡你或許會選擇以肉眼來辨識，但現實是當面對大量或者複雜的模型時，會顯得效率太差，所以最好由電腦進行這樣的辨識工作。

可換作是電腦，它要如何辨識呢？畢竟他本身就不存在像人眼那樣的辨識模型。在這裏提供一個方法來幫助電腦辨識，這個方法的名稱如同標題那樣，而普遍會以他的方法特色而為他取別名：龜兔賽跑算法。

顧名思義，這個算法會假設一隻烏龜和一隻兔子在這個結構進行賽跑，烏龜每次只能走一個節點，而兔子只能走二個節點，他們只要跑下去肯定能到循環裡，最終如果他們能在循環中碰面或者在同一點會合的話，就能表示這個結構存在著循環。(如下圖所示)


然而，如果兔子走到結構中的終點卻沒跟烏龜會合的話，那就表示著結構不存著循環。(如下圖)


### 程式碼以及複雜度

程式碼連結：bit.ly/2FKotVP

使用EAFP程式碼風格來取代過度的if-else檢查，並從中提升速度，另外先讓在try區塊中的兔子多走一步以避免while迴圈判斷到錯誤的情況，同時這樣子的移動方式並不會改變兔子和烏龜的會合結果，只不過變成M+1個循環外節點的情況來移動。

時間複雜度：考慮該方法應用在不存在循環以及存在循環的場景中，能得到時間複雜度範圍會是O(N1+N2)~O(N)，其中的N1是循環外的起點1至循環內的起點2的距離，而N2是循環內的起點2至烏龜與兔子預計會合的點之間的距離（如下圖），而N為節點的總共數量，其中根據以下的第六個觀察結果會發現N2是在烏龜花不到半圈得到的數值，所以N≥N1+N2。


空間複雜度：該方法本身不需要向系統索求額外記憶體空間或者內存來進行判斷，所以空間複雜度會是原本一般執行程式碼所需要用到的記憶體大小，也就是O(1)。

最後您會不會萌生懷疑，這方法真的能行得通嗎？或許您會想 "我只要知道如何運用這方法，不需要知道太多"，那麼在這裏我會直接以"行得通"來回答你的疑惑並建議您就此停步，因爲接下來進入大家比較討厭的階段 - 證明

## 方法證明

首先我們先來考慮擁有循環的結構(如下圖)，在循環之前可能會有N個點或者沒存在任何節點，而這N的值會影響著烏龜和兔子在循環中的初始位置，再來為了很好瞭解影響，設定了數字來表示循環中的第幾個節點，以0到λ-1來命名，而λ則是定義成循環中的長度-節點數，在這裡λ=10。


首先我們先考慮著N=0時，兔子和烏龜會在循環的起點會合，並從那裡開始進行他們的賽跑。


根據兔子走兩步和烏龜走一步的前提，當兔子走完一圈時，烏龜才走半圈，而兔子在走完一圈時，這時烏龜才走完一圈，此時他們倆就在一開始的點會合。

在這裡，我們會發現幾個有趣的觀察結果：

1. 兔子得走完一圈才有辦法跟烏龜會合(p.s 他們倆不動也能會合XD，但這不是在該方法的討論範圍內)
2. 兔子H的步數會是烏龜T的步數之一倍，換言之，H=2T。
3. 延伸第二個結果，若沒有循環的存在，他們倆就可能沒辦法會合，但若是給予循環的存在，等同強制添加mod λ運算至H和T上才能判斷他們是否會合（如下式），而如果都是一樣的話，便是代表在循環中會合；但如果都不是一樣，便是還未會合。


或者


統整這三個觀察結果，我們會發現只要T=λ 代入上式，兔子和烏龜會在第0個節點會合。接下來我們思考另一種情況，如果N=1時，這種代入結果會不會有所不同？


從上圖可以觀察出當烏龜進入循環時的位置不是在與兔子在同一個節點，而是相差一個節點，這對於N=0所得出的觀察結果而言，兔子還是得走完一圈才有辦法和烏龜在同一點，而且也不影響著兔子和烏龜原本要走的步數，由於當烏龜進入循環時的兔子所在位置不同而改變了第三種觀察結果

首先兔子在循環中的位置會變成：


那麼這個新位置會不會影響和烏龜在同一點會合呢？只要我們按照圖上位置來模擬他們移動，最後會發現他們的確會在同一點會合，只是位置變成第λ-1個位置或者最後一個位置-第9個位置。

那麼第三個觀察結果會變成如下所示：



接著我們再來思考一下N=2時，會有什麼樣的變化


同樣的，由於只是單純增加循環外面的節點，不會影響著第一、二個觀察結果，而第三個結果中的兔子預期位置


，接著我們只要按照圖上位置來模擬他們移動就會發現他們的確也是會在同一點上會合，但這次是第λ-2個節點或者第8個節點上會合。如果考慮成N=3時，會發現會在第λ-3個節點或者第7個節點上會合，而N=4時，會發現在第λ-4個節點或者第6個節點上會合。

那麼最後我們來試著考慮著N=M的情況，而M的範圍為\[1,∞\)，而定義成這範圍是由於我們只限定於不存在循環以外的點以及存在M個循環以外的點，在此只討論後者，前者已在N=0討論過。


在這N=M的情況下，會使得兔子預期位置變成：


在這裡我們還不確定這種情況是否同樣地使烏龜和兔子會在同一點會合，所以我們先假設他們肯定能在某一點會合來找出矛盾或者驗證其正確性，換言之，先定義出這式子：


或者


根據前面所述的第ㄧ、二觀察結果，兔子必須得至少繞ㄧ圈才有機會與烏龜會合，但這樣單純繞幾圈也只是與烏龜保持M~(0.5λ+M)個節點的距離，所以兔子和烏龜必須得多走個幾步才有機會會合，所以式子會變成如下：

 (烏龜繞了$N_1$圈又$N_2$步)


根據mod λ，我們可以化簡成：


根據先前N=2~4情況得到的觀察結果，會發現都會在第λ-N個節點會合，那麼同樣地將其結果套用在上式時，會發現式子變成




而這相當於在第λ-M個節點或者第λ-N個節點會合


從這樣推論驗證了N在\[1,∞\)範圍內的節點數所構成循環時可以使兔子和烏龜在第λ-N個節點會合。

### 其中λ-M中的λ其實原本是考慮成N'λ，但由於最後還是會因爲mod λ而跟λ-M的最後結果一樣，且如果寫N'λ-M的話，會不容易理解，在這裏簡化成最後解。


此外，如果讀者願意花更多時間觀察的話，只要畫個圖並標示起點、會合點、距離的話(如下圖）


，會發現只要N與λ-N相加就能構成循環長度，換言之，


從會合點到起點2的距離剛好是N個節點。

還有如果我們限制烏龜只能在循環內走不到一圈來和兔子會合，會得到一個有趣的觀察結果，其中烏龜走不到半圈時會使兔子永遠會合不了，因此烏龜的步數要滿足走不到一圈以及會合的條件必須是半圈以上至一圈的範圍，所以，原本的式子會改變成如下：



簡化的話，會得到


同時我們可以用先前得到的驗證結果來反證這樣子是否出現矛盾，首先右邊的式子在這前提下，必須等於-M或者λ-M，那麼


代入原式會形成：


這樣子的結果等同於先前驗證結果，換言之，烏龜只需要繞半圈以上至一圈的距離就能和兔子會合。

### 先前我們假設烏龜和兔子會花好幾圈又幾個節點才能使他們會合，在這好幾圈又幾個節點的範圍內包含了無數個排列組合，比如2圈又5個節點，現在我們利用限制發現了其實烏龜走不到半圈就能會合。但這過程中，兔子還是得至少走一圈才能會合。

稍微統整目前得到觀察結果，我們可以得到：
1. 兔子得走完一圈才有辦法跟烏龜會合(p.s 他們倆不動也能會合XD，但這不是在該方法的討論範圍內)
2. 兔子H的步數會是烏龜T的步數之一倍，換言之，H=2T。
3. 延伸第二個結果，若沒有循環的存在，他們倆就可能沒辦法會合，但若是給予循環的存在，等同強制添加mod λ運算至H和T上才能判斷他們是否會合（如下式），其中M為循環外的節點數，如果都是一樣的話，便是代表在循環中會合；但如果都不是一樣，便是還未會合。


4. 延伸第三個觀察結果，會發現兔子和烏龜的會合點會是第λ-N個節點或者第λ-M個節點
5. 循環起點到會合點的距離可以和循環以外的節點數構成循環長度，換言之，λ = 循環起點到會合點的距離+ 循環以外的節點數。
6. 烏龜只需要繞半圈以上至一圈的距離就能和兔子會合。

前面兩個結果因爲本身不受循環以外的節點數影響，所以不會進行變動，但原本第三個結果會隨之影響，使之擴展成考慮成M個循環以外的節點，而第4~5個結果則是因爲第三個結果的推論過程而新增過來的。

### 總結
我們稍微介紹這方法以及應用場景，並且在最後證明這方法的可行性，同時從證明過程得到六個有趣結果。