algorithm - フロイドの循環検出アルゴリズム-2つのポインターが必要ですか？

Question

私は今日、フロイドの循環検出アルゴリズムを実行していましたが、疑問がありました。なぜ彼は2つのポインターを必要とし、それらを異なる速度で動かすのでしょうか？

代わりに、2つのポインターを作成して、1つを静的に保ち、そのポインターを別のポインターと比較して、それをインクリメントすることができますか？それでも、サイクルを正しく見つけることができるということですか？

Answer 1

移動する必要がある理由は、サイクルが必ずしもノードのリスト全体をループする必要がないためです。

たとえば、4つのノードA-> B-> C->D->Bがあるとします。

1つのポインターをAに向けたままにしておくと、サイクルを検出できなくなります。

Answer 2

その理由は、サイクルから外れるブランチからポインターを取り除くために、後ろにある（ゆっくりと増加する）ポインターを増やす必要があるためです。

例えば。エッジA=>B、B => C、C => A、D => B、E=>D。

両方のポインターがEから始まると仮定します。一方のポインターを変更しない場合、もう一方のポインターはE => D => B => C => A => B => C => ...になり、 E。

他の人があなたが同じアルゴリズムの複雑さを得ることができないと言うとき、彼らはあなたがすべての単一の頂点から始めなければならないことを意味します（それはより遅いです）。高速/低速ポインタ方式では、グラフの各「コンポーネント」から1回だけ開始する必要があります。コンポーネントは、互いに接続されているすべての頂点です。コンポーネントが分離しているということは、頂点がエッジで接続されていないことを意味します。

低速ポインタを増やすと、A => B=>Cサイクルにもなります。

そして、ポインタの変更の効果的な違いはわずか1であるため、見逃すことはありません。高速ポインタが低速ポインタに追いついている場合、それらの間の距離は反復ごとに1ずつしか変化しません。したがって、最終的に距離は0に達します。