フロイドの循環検出アルゴリズム(Floyd's cycle-finding algorithm)

漫画などでよくある「同じ道をぐるぐる回っている」気がしたとき、どのようにしてそれを確かめることができるでしょう？一つの方法を紹介します。二手に分かれ、一方は歩いて道を進み、もう一方は走って道を進みます。もし同じ道をぐるぐる回っているのだとすれば、走っている方が歩いている方にいつか追いつきます。ぐるぐる回っているのではなく出口があった場合は、先に着く走っている方が出口で待っていれば、歩いている方がいつか追いつき出口で合流できます。この記事では、私が大好きなこのアイデアを使ったアルゴリズムを紹介します。

問題

連結リストLが与えられたとき、Lがサイクル(循環)を持つ場合はtrueを、そうでない場合はfalseを返しなさい

サイクルを持つとは、下の図のように、Lのi番目のノードをL_iとすると、i >= kを満たす任意のiに対しL_(i+n)=L_iが満たされるようなk, nが存在するということです。下記の図の場合は、iを1から数えた場合k = 3, n = 3です。

考え方

2つのポインタ（変数）を使って連結リストを走査します。一方のポインタslowはL上を1ノードずつ進め、他方のポインタfastはL上を2ノードずつ進めます。サイクル（循環）が存在しない場合、 fast がリストの末尾に達して終了します。サイクルが存在する場合、サイクル内で fast が slow に追いつくことでサイクルを検出できます。下記のイメージです。

アルゴリズム

アルゴリズムの形で書き直します。
Step1
　二つの変数 fast,slow にLの最初のノードを格納する
Step2
　fast を二つ次のノードに、 slow を一つ次のノードに進める
Step3
　fast と slow が同じノードを指していた場合、trueを返して終了する。そうでない場合、 fast に二つ次のノードが存在する場合はStep2に戻り、存在しない場合はfalseを返して終了する。

Python3.0による実装は下記のようになります。

def hasCycle(head):
   fast = slow = head;
   while fast and fast.next:
       fast = fast.next.next
       slow = slow.next
       if fast == slow:
           return True
   return False

なお、headは連結リストを表現した下記クラスのインスタンスで、連結リストの最初のノードを表すとします。

 ​class Node:
    def __init__(self, x):
        self.val = x
        self.next = None

計算量

時間計算量はO(n)
時間計算量はLの長さを n として、O(n) です。
(サイクルが存在しない場合)
fast が最後のノードまで到達して終了するため、 n/2 stepで終了します。
(サイクルが存在する場合)
slowがサイクルの開始点に到達した時点でfastがどこにいた場合でも、slowがサイクル部分を一度通る時点（つまり n step目）までの間にfastはサイクル部分を二度通過するため、追いついてループ検出が終了します。そのため、高々 n step で終了します。

空間計算量はO(1)
2つのポインタ（変数）を使うのみなので、空間計算量は O(1) です。

本当にFloydのアルゴリズム？

このアルゴリズムについて調べると、フロイドの1967年の論文[1]で発明されたという説明がされていること多いようです。ですが、当該論文にはこのアルゴリズムに関する記載はなく、記載されているのは有向グラフ中のサイクルを列挙するアルゴリズムです。英語版Wikipedia[2]では明確な発見者のいない定理ではないかとの指摘もあります。

サイクルの開始ノードを発見する

このアルゴリズムは、シンプルで計算量に優れているだけでなく、様々な応用があるところも魅力の一つです。元のアルゴリズムを少し拡張するだけで、サイクルの開始ノードを発見することができます。

問題
連結リストLが与えられたとき、Lがサイクル(循環)を持つ場合はサイクルの先頭のノードを、そうでない場合はnullを返しなさい

考え方

準備
解析のためにいくつかの用語を定義します。
・先頭ノードを0番目とし、i 番目のノードを x_i
・見つけたいサイクルの開始ノードを x_s
・サイクルの長さをl
・fastとslowは k step目に出会う（x_2kとx_k が同一ノード）とする
この時、下記が成り立ちます。
・ k=ln(nは整数) : fastとslowの進んだ距離の差2k−k=kはサイクルの長さの整数倍。サイクル開始までがすごーく長くてサイクルが短いと、nが大きくなる、つまりfastはサイクルを何度も回ってからslowに出会います。
・ x_s=x_s+ln : サイクル部分を周回すると開始点に戻る
絵にするとこんな感じです。

開始点を見つける
k step目にサイクルを検出したのち、fastのみを最初のノードに戻し、今度はfastもslowも1ノードずつ進めます。するとs step後にfastとslowは再びサイクルの開始ノードx_sで出会います。なぜなら s step後、fastは x_s に、 slow は x_(k+s)=x_(ln+s)=x_s にいるからです。

アルゴリズム

Step1
　二つの変数 fast,slow にLの最初のノードを格納する
Step2
　fast を二つ次のノードに、 slow を一つ次のノードに進める
Step3
　fast と slow が同じノードを指していた場合、Step4に進む。そうでない場合、 fast に2つ先のノードが存在する場合はStep2に戻り、存在しない場合はfalseを返して終了する。
Step4
　fast に Lの最初のノードを格納する
Step5
　fast,slow をそれぞれ次のノードに進める
Step6
　fast と slow が同じノードを指していた場合はfastが指すノードを返し、そうでない場合はStep5に戻る

Python3.0による実装は下記のようになります。

def detectCycle(head):
   fast = slow = head
   while fast and fast.next:
       fast = fast.next.next
       slow = slow.next
       if fast == slow:
           fast = head
           while fast != slow:
               fast = fast.next
               slow = slow.next
           return fast
   return None

おわりに

どこまで続いているかわからない連結リストの情報を二つの変数のみを使って探るという点が非常に面白いアルゴリズムだと思います。元のアルゴリズムの応用として、こんな問題も解くことができますので、考えてみてください。

問題
サイクルを持たない連結リストLが与えられたとき、Lの真ん中のノードを返しなさい。真ん中のノードとは、Lのi番目のノードをL_i（先頭ノードはL_0）、Lの長さをnとしたとき、nが偶数の時はL_(n/2)、nが奇数の時はL_((n-1)/2)を指すものとする。

参考文献

[1] Floyd, R.W. (1967), “Nondeterministic Algorithms”, J. ACM, 14 (4): 636–644
[2] “Cycle detection”, Wikipedia. https://en.wikipedia.org/wiki/Cycle_detection