檢視 Floyd判圈算法的原始碼

'''Floyd 判圈算法'''('''Floyd Cycle Detection Algorithm''')，閣稱'''龜兔走相逐'''('''Tortoise and Hare Algorithm''')，是一个會當佇有限狀態機、迵天代函數抑是鍊表頂判斷是毋是存在環，求出該環的起點佮長度的算法。該算法據高德納稱由美國科學家羅伯特 ・ 洛洛伊德發明，但是這一算法並無出現佇咧羅伯特 ・ 洛洛伊德公開發表的對作當中 [一]。

如果有限狀態機、迵天代函數抑是鍊表頂存在環，若佇某一个環上以無仝速度進前的兩个指針必定會佇某一个時刻相拄。同齊顯然的，若對仝一个起點 ( 就算這个起點無佇某一个環上 ) 同時開始以無仝速度進前的兩个指針最終相拄，遐爾仔會當判定存在一个環，而且會當求出二者相拄所在的環境佮長度。

==算法==

===算法講===

如果有限狀態機、迵天代函數抑是鍊表存在環，遐爾仔一定存在一个起點會當到甲某一个環的某處 ( 這个起點嘛會當佇某一个環上 )。

初狀態之下，準講已經知影某一个起點節點 S。現設兩个指針 t 和 h，共𪜶攏指向 S。

接咧，同時予 t 和 h 向前捒入去，但是二者的速度無仝款：t 逐家進一步，h 進二步。只要兩者攏會當進前而且無相拄，就按呢保持兩者的推進。當 h 無法度行入去，即到達某一个無後繼的節點的時，就會當確定講對 _ S _ 出發袂拄著環。就反起來 t 佮 h 閣再相拄時，就會當確定講對 S 出發一定會進入某一个環，設其為環 C。

若確定講存在某一个環，就會當求此環的起點佮長度。

等述算法拄判斷出存在環 C 時，顯然 t 和 h 是仝一節的點，設其為節點 M。顯然，干焦需令 h 無法度，而且 t 不斷捒入來，終其尾會閣倒轉來點 M，統計這改 t 推進的步數，顯然這就是環 C 的長度。

為著欲求出環 C 的起點，只要令 h 猶原平均佇咧節點 M，而令 t 倒轉來點節點 S，現此時 h 佮 t 之間距為環 C 長度的整數倍。隨後，同時予 t 和 h 向前捒入去，而且保持二者的速度相𫝛：t 逐家進一步，h 進一步。繼續應該過程一直到 t 佮 h 閣一改相拄，設這改相拄的時陣佇仝一節點 P，則節點 P 為著從節點 S 出發所到的環 C 的第一个節點，即環 C 的一个起點。

===偽代碼===

` ` `
一 _ t _   :='''&'''_ S _
二 _ h _   :='''&'''_ S _ / / 令指針 _ t _ 和 _ h _ 攏指向起點節點 _ S _。
三'''repeat'''
四 	 _ t _   :=_ t _-> next
五 	 _ h _   :=_ h _-> next
六 	'''if'''_ h _ is not NULL / / 愛注意這一判斷一般袂使省略七 		 _ h _   :=_ h _-> next
八'''until'''_ t _=_ h _'''or'''_ h _=NULL
九'''if'''_ h _   !=NULL / / 若準儉佇咧環境十 	 _ n _   :=零十一 	'''repeat'''/ / 求環的度十二 		 _ t _   :=_ t _-> next
十三 		 _ n _   :=_ n _ + 一十四 	'''until'''_ t _=_ h _
十五 	 _ t _   :='''&'''_ S _ / / 求環的一个起點十六 	'''while'''_ t _   !=_ h _
十七 		 _ t _   :=_ t _-> next
十八 		 _ h _   :=_ h _-> next
十九 	 _ P _   :='''\'''* _ t _
` ` `

===算法複雜度===

====時間複雜度====

注意著做指針 t 達到環 C 的一个起點節點 P 時 ( 現此時指針 h 顯然佇環 C 上 )，了指針 t 上濟干焦可能行一輪。若設節點 S 到 P 距離為 $ m $，環 C 的長度為 $ n $，則時間複雜度做 $ O ( m + n ) $，是線性時間的算法。[二]

====空間複雜度====

干焦需要創立指針 t、指針 h，保存環長 n、環的一个起點 P。空間複雜度做 $ O ( 一 ) $，是常數空間的算法。[三]

==應用==

對有限狀態機和鍊表，會當判斷對某一个起點開始敢會當轉來遮訪問過運行的過程當中的某一个狀態佮節點。

嘿迵天代函數，會當去判斷著無佇咧周期，以及求出其上細漢拄好周期。

==相關算法==

雖然 Floyd 判圈算法已經達到線性時間複雜度佮常數空間複雜度，猶毋過 Brent 判圈算法將減細漢時間複雜度的常數係數，平均時間比起來 Floyd 判圈算法少百分之三十六。[四]

==參考連結==

* Floyd's Cycle Detection Algorithm ( The Tortoise and the Hare )
* Brent's Cycle Detection Algorithm ( The Teleporting Turtle )
* Floyd's cycle-finding algorithm

[[分類: 待校正]]