32

リンクされたリストにサイクルがあるかどうかを判断するための最良の (停止) アルゴリズムは何ですか?

[編集] 時間と空間の両方の漸近的複雑度の分析は、答えをよりよく比較できるようになるでしょう。

[編集] 元の質問は、outdegree > 1 のノードに対処することではありませんでしたが、それについていくつかの話があります。その質問は、「有向グラフでサイクルを検出するための最良のアルゴリズム」の行に沿っています。

4

13 に答える 13

51

リストを反復する 2 つのポインターを持ちます。一方をもう一方の 2 倍の速度で反復させ、各ステップでの位置を比較します。私の頭の上から、次のようなもの：

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n)、これはあなたが得ることができるのと同じくらい良いです。

于 2008-08-29T09:34:18.277 に答える
2

前提条件: リストのサイズを追跡します (ノードが追加または削除されるたびにサイズを更新します)。

ループ検出:

  1. リストサイズをトラバースするときにカウンターを保持します。

  2. カウンタがリスト サイズを超える場合は、サイクルが発生する可能性があります。

複雑さ: O(n)

注: カウンターとリスト サイズの比較、およびリスト サイズの更新操作は、スレッド セーフにする必要があります。

于 2011-05-16T22:18:58.840 に答える
1

2 つのポインター *p と *q を取り、両方のポインターを使用してリンクされたリスト "LL" のトラバースを開始します。

1) ポインター p は、毎回前のノードを削除し、次のノードを指します。

2) ポインター q は、毎回順方向のみに移動します。

条件：

1) ポインタ p が null を指しており、q が何らかのノードを指している: ループが存在する

2) null を指す両方のポインター: ループはありません

于 2015-07-24T10:17:57.277 に答える
0

リストの先頭で 2 つのポインターが初期化されます。1 つのポインターは各ステップで 1 回前進し、もう 1 つのポインターは各ステップで 2 回前進します。高速のポインターが低速のポインターと再び出会うと、リストにループが発生します。それ以外の場合、より速い方がリストの最後に到達してもループはありません。

以下のサンプル コードは、このソリューションに従って実装されています。高速のポインタは pFast で、低速のポインタは pSlow です。

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

このソリューションは、私のブログで入手できます。ブログで議論されている別の問題があります: リストにサイクル/ループがある場合のエントリ ノードとは何ですか?

于 2012-12-28T13:35:51.807 に答える
0

これを確認するには、すべてのノードにアクセスする必要があります。これは再帰的に行うことができます。既に訪問したノードへの訪問を停止するには、「既に訪問済み」というフラグが必要です。もちろん、これはループを与えません。したがって、ビット フラグの代わりに数値を使用します。1 から開始します。接続されているノードを確認し、これらを 2 としてマークし、ネットワークがカバーされるまで再帰します。ノードをチェックしているときに、現在のノードよりも 1 つ以上少ないノードに遭遇した場合は、サイクルが発生しています。周期の長さは差によって与えられます。

于 2008-09-26T15:05:15.297 に答える
0

この場合、OysterD のコードが最速のソリューションになります (頂点カラーリング)

それは本当に私を驚かせるでしょう。私のソリューションは、リストを介して最大 2 つのパスを作成し (最後のノードが最後から 2 番目のロードにリンクされている場合)、一般的なケース (ループなし) では 1 つのパスのみを作成します。ハッシュなし、メモリ割り当てなしなど。

于 2008-08-29T09:52:44.037 に答える
0

この場合、OysterD のコードが最速のソリューションになります (頂点カラーリング)

それは本当に私を驚かせるでしょう。私のソリューションは、リストを介して最大 2 つのパスを作成し (最後のノードが最後から 2 番目のロードにリンクされている場合)、一般的なケース (ループなし) では 1 つのパスのみを作成します。ハッシュなし、メモリ割り当てなしなど。

はい。調合が完璧ではないことに気付き、書き直しました。私は今でも、巧妙なハッシングがより高速に実行できると信じています。ただし、あなたのアルゴリズムが最善の解決策だと思います。

私のポイントを強調するだけです。頂点の色付けは、最新のガベージコレクターによって依存関係のサイクルを検出するために使用されるため、非常に実際の使用例があります。ほとんどの場合、ビット フラグを使用して色付けを実行します。

于 2008-08-29T09:58:35.397 に答える
0

これは、ポインターアドレスを保存するためにハッシュテーブル（実際には単なるリスト）を使用するソリューションです。

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False
于 2016-07-19T08:16:32.163 に答える
0

ハッシュ テーブルを使用して、既に表示されているノードを格納するのはどうでしょうか (リストの最初から順に見ていきます)。実際には、O(N) に近い値を達成できます。

それ以外の場合、ハッシュ テーブルの代わりに並べ替えられたヒープを使用すると、O(N log(N)) が達成されます。

于 2008-08-29T09:33:50.697 に答える
0

反復する以外に方法があるのではないかと思います-前進するときに配列にデータを入力し、現在のノードが配列に既に存在するかどうかを確認します...

于 2008-08-29T09:34:45.017 に答える
0

サイクルが最初を指していない場合、Konrad Rudolph のアルゴリズムは機能しません。次のリストでは、1->2->3->2 の無限ループになります。

DrPizza のアルゴリズムは間違いなく最適な方法です。

于 2008-08-29T09:46:24.677 に答える