有向グラフ内のサイクルを検出するための効率的なアルゴリズムはありますか?
実行する必要があるジョブのスケジュールを表す有向グラフがあります。ジョブはノードであり、依存関係はエッジです。循環依存関係につながるこのグラフ内の循環のエラー ケースを検出する必要があります。
Peauters
質問する
358694 次
14 に答える
205
Tarjan の強連結成分アルゴリズムにはO(|E| + |V|)時間の複雑性があります。
その他のアルゴリズムについては、ウィキペディアの強連結成分を参照してください。
于 2008-11-04T11:35:04.593 に答える
81
これがジョブのスケジュールであることを考えると、ある時点でそれらを提案された実行順序に並べ替えることになると思います。
その場合、トポロジカルソートの実装は、いずれにしてもサイクルを検出する可能性があります。UNIXtsortは確かにそうです。したがって、別のステップではなく、tsorting と同時にサイクルを検出する方が効率的である可能性が高いと思います。
そのため、「ループを最も効率的に検出するにはどうすればよいか」という質問ではなく、「最も効率的に tsort を行うにはどうすればよいか」という問題になる可能性があります。答えはおそらく「ライブラリを使用する」ですが、次のウィキペディアの記事では失敗しています。
1 つのアルゴリズムの疑似コードと、Tarjan による別のアルゴリズムの簡単な説明があります。どちらもO(|V| + |E|)時間の複雑さを持っています。
于 2008-11-04T11:50:46.980 に答える
35
これを行う最も簡単な方法は、グラフの深さ優先トラバーサル (DFT) を実行することです。
グラフにn頂点がある場合、これはO(n)時間計算量アルゴリズムです。各頂点から開始して DFT を実行する必要がある可能性があるため、全体の複雑さは になりO(n^2)ます。
現在の depth first traversal のすべての頂点を含むスタックを維持する必要があります。その最初の要素はルート ノードです。DFT 中に既にスタックにある要素に遭遇した場合は、循環があります。
于 2009-04-21T01:14:14.680 に答える
29
DFS から開始します。DFS中にバックエッジが検出された場合にのみ、サイクルが存在します。これは、ホワイトパス定理の結果として証明されています。
于 2010-12-30T20:02:16.603 に答える
9
「訪問済み」プロパティをノードに追加できない場合は、セット (またはマップ) を使用して、訪問済みのすべてのノードをセットに追加します。オブジェクトの一意のキーまたはアドレスを「キー」として使用します。
これにより、循環依存関係の「ルート」ノードに関する情報も得られます。これは、ユーザーが問題を修正する必要がある場合に役立ちます。
別の解決策は、実行する次の依存関係を見つけようとすることです。そのためには、現在の場所と次に何をする必要があるかを思い出せるスタックが必要です。実行する前に、依存関係が既にこのスタックにあるかどうかを確認してください。そうであれば、サイクルを見つけたことになります。
これは O(N*M) の複雑さを持っているように見えるかもしれませんが、スタックの深さが非常に限られており (N が小さいため)、M は「実行済み」としてチェックできる依存関係ごとに小さくなることを覚えておく必要があります。葉が見つかったら検索を停止できます (したがって、すべてのノードをチェックする必要はありません-> M も小さくなります)。
MetaMake では、グラフをリストのリストとして作成し、それらを実行するたびにすべてのノードを削除して、自然に検索ボリュームを削減しました。実際に独立したチェックを実行する必要はありませんでした。通常の実行中にすべて自動的に行われました。
「テスト専用」モードが必要な場合は、実際のジョブの実行を無効にする「dry-run」フラグを追加するだけです。
于 2008-11-04T12:15:46.370 に答える
4
私はこの問題をsml（命令型プログラミング）で実装しました。これが概要です。インディグリーまたはアウトディグリーが0のすべてのノードを検索します。このようなノードをサイクルの一部にすることはできません（したがって、ノードを削除してください）。次に、そのようなノードからすべての着信エッジまたは発信エッジを削除します。このプロセスを結果のグラフに再帰的に適用します。最後にノードまたはエッジが残っていない場合、グラフにはサイクルがありません。そうでない場合は、サイクルがあります。
于 2013-01-24T01:49:29.213 に答える
2
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-lengthこのソリューションは、特に 4 つの長さに最適です:)
また、physウィザードは、O（V ^ 2）を実行する必要があると言います。O(V)/O(V+E)だけあればいいと思います。グラフが接続されている場合、DFS はすべてのノードを訪問します。グラフがサブ グラフを接続している場合、このサブ グラフの頂点で DFS を実行するたびに、接続されている頂点が検出され、DFS の次の実行でこれらを考慮する必要はありません。したがって、頂点ごとに実行される可能性は正しくありません。
于 2013-02-16T12:05:38.397 に答える
1
私が行う方法は、訪問した頂点の数を数えて、トポロジカル ソートを行うことです。その数が DAG 内の頂点の総数よりも少ない場合は、サイクルがあります。
于 2008-11-04T13:35:57.050 に答える
0
DFS が既に訪れた頂点を指すエッジを見つけた場合、そこに循環があります。
于 2013-05-12T07:16:29.210 に答える
-12
グラフがこの性質を満たす場合
|e| > |v| - 1
その場合、グラフには少なくとも 1 つのサイクルが含まれます。
于 2010-10-28T10:33:15.100 に答える