有向グラフ内のサイクルを検出するための最適なアルゴリズム

StackOverflow https://stackoverflow.com/questions/261573

質問

有向グラフ内のすべてのサイクルを検出するための最も効率的なアルゴリズムは何ですか?

実行する必要があるジョブのスケジュールを表す有向グラフがあります。ジョブはノード、依存関係はエッジです。循環依存関係につながるこのグラフ内の循環のエラーケースを検出する必要があります。

役に立ちましたか？

解決

Tarjanの強く接続されたコンポーネントアルゴリズムには O（| E | + | V |）時間の複雑さ。

他のアルゴリズムについては、Wikipediaの強力に接続されたコンポーネントを参照してください。

他のヒント

これがジョブのスケジュールであるということを考えると、ある時点で、あなたはそれらを提案された実行順序にソートしようとしていると思われます。

その場合、 トポロジーソート の実装はいずれにしても、サイクルを検出します。 UNIX tsort は確かにそうです。したがって、別のステップではなく、tsortingと同時にサイクルを検出する方が効率的であると思われます。

「ループを最も効率的に検出する方法」ではなく、「どのようにして最も効率的にtsortを実行するのか」という質問になります。おそらく「ライブラリを使用する」という答えがありますが、次のウィキペディアの記事に失敗しています：

  

http://en.wikipedia.org/wiki/Topological_sorting

には、あるアルゴリズムの擬似コードと、Tarjanの別のアルゴリズムの簡単な説明があります。両方とも O（| V | + | E |）時間の複雑さを持っています。

DFSで開始：DFSの間にバックエッジが検出された場合にのみ、サイクルが存在します。これは、ホワイトパス定理の結果として証明されています。

最も簡単な方法は、グラフの深さ優先走査（DFT）を行う ことです。

グラフに n の頂点がある場合、これは O（n）時間複雑度アルゴリズムです。各頂点から開始してDFTを実行する必要があるため、合計の複雑度は O（n ^ 2）になります。

最初の要素がルートノードである現在の深さ優先走査のすべての頂点を含むスタックを維持する必要があります。 DFT中に既にスタックにある要素に出会った場合、サイクルがあります。

私の意見では、有向グラフのサイクルを検出するための最も理解可能なアルゴリズムはgraph-coloring-algorithmです。

基本的に、グラフの色付けアルゴリズムはグラフをDFS方式で探索します（深さ優先探索、つまり、別のパスを探索する前にパスを完全に探索します）。バックエッジが見つかると、グラフにループが含まれているとマークされます。

グラフの色付けアルゴリズムの詳細な説明については、次の記事をお読みください： http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

また、JavaScriptでグラフの色付けの実装を提供します https：/ /github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

「訪問済み」を追加できない場合プロパティをノードに追加し、セット（またはマップ）を使用して、既にセットに含まれていない限り、訪問したすべてのノードをセットに追加します。一意のキーまたはオブジェクトのアドレスを＆quot; key＆quot;として使用します。

これは、「ルート」に関する情報も提供します。ユーザーが問題を修正する必要があるときに役立つ循環依存関係のノード。

別の解決策は、実行する次の依存関係を見つけることです。そのためには、現在の場所と次に何をする必要があるかを思い出せるスタックが必要です。実行する前に、このスタックに依存関係が既にあるかどうかを確認してください。もしそうなら、あなたはサイクルを見つけました。

これはO（N * M）の複雑さを持っているように見えるかもしれませんが、スタックの深さは非常に限られているため（Nは小さい）、Mは依存関係ごとに小さくなり、＆quot ;実行済み＆quot;さらに、リーフが見つかったら検索を停止できます（したがって、すべてのノードをチェックする必要はありません決して-＆gt; Mも小さくなります）。

MetaMakeでは、グラフをリストのリストとして作成し、実行時にすべてのノードを削除しました。これにより、検索ボリュームが自然に削減されました。実際に独立したチェックを実行する必要はありませんでした。通常の実行中にすべて自動的に行われました。

「テストのみ」が必要な場合モードでは、「ドライラン」を追加するだけです。実際のジョブの実行を無効にするフラグ。

有向グラフ内のすべてのサイクルを多項式時間で見つけることができるアルゴリズムはありません。有向グラフにn個のノードがあり、ノードのすべてのペアに相互接続があるとします。これは、完全なグラフがあることを意味します。したがって、これらのn個のノードの空でないサブセットはサイクルを示し、そのようなサブセットは2 ^ n-1個あります。したがって、多項式時間アルゴリズムは存在しません。     したがって、グラフ内の有向サイクルの数を示すことができる効率的な（非愚かな）アルゴリズムがあると仮定すると、まず強い連結成分を見つけ、次にこれらの連結成分にアルゴリズムを適用できます。サイクルはコンポーネント内にのみ存在し、コンポーネント間には存在しないため。

DFSが既に訪れた頂点を指すエッジを見つけた場合、そこにサイクルがあります。

の補助定理 22.11 によると、 コーメンら、 アルゴリズムの概要 (CLRS):

有向グラフ G は、G の深さ優先検索でバック エッジが得られない場合に限り、非巡回です。

これはいくつかの回答で言及されています。ここでは、CLRS の第 22 章に基づいたコード例も提供します。グラフの例を以下に示します。

enter image description here

深さ優先検索用の CLRS の疑似コードは次のようになります。

enter image description here

CLRS 図 22.4 の例では、グラフは 2 つの DFS ツリーで構成されています。ノードで構成されるもの あなた, v, バツ, 、 そして y, 、およびその他のノード w そして z. 。各ツリーには 1 つのバック エッジが含まれます。からの1つ バツ に v そしてもう一つから z に z （自己ループ）。

重要な認識は、次の場合にバック エッジに遭遇するということです。 DFS-VISIT 近傍を反復しながら関数を実行する v の u, 、ノードが次の状態に遭遇します。 GRAY 色。

次の Python コードは、CLRS の疑似コードを適応させたものです。 if サイクルを検出する句が追加されました。

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in discovered and v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

この例では、 time CLRS の疑似コードはサイクルの検出のみに関心があるため、キャプチャされません。エッジのリストからグラフの隣接リスト表現を構築するための定型コードもいくつかあります。

このスクリプトを実行すると、次の出力が出力されます。

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

これらは、まさに CLRS 図 22.4 の例のバック エッジです。

これを行う方法は、トポロジカルソートを行い、訪れた頂点の数を数えることです。その数がDAGの頂点の総数より少ない場合、サイクルがあります。

この問題をsml（命令型プログラミング）で実装しました。ここに概要を示します。 indegreeまたはoutdegreeが0であるすべてのノードを見つけます。そのようなノードはサイクルの一部であることができません（それらを削除してください）。次に、そのようなノードからすべての着信エッジまたは発信エッジを削除します。 このプロセスを結果のグラフに再帰的に適用します。最後にノードまたはエッジが残っていない場合、グラフにはサイクルがありません。それ以外はありません。

https://mathoverflow.net/questions/16393/finding-a-cycle -of-fixed-length 長さ4の場合、このソリューションが特に最適です：）

また、physウィザードは、O（V ^ 2）を実行する必要があると言います。 O（V）/ O（V + E）だけが必要だと思います。 グラフが接続されている場合、DFSはすべてのノードを訪問します。グラフにサブグラフが接続されている場合、このサブグラフの頂点でDFSを実行するたびに、接続された頂点が見つかり、DFSの次の実行でこれらを考慮する必要はありません。したがって、各頂点で実行される可能性は正しくありません。

おっしゃるように、ジョブのセットがあります。特定の順序で実行する必要があります。ジョブのスケジューリングに必要な順序（または直接非循環グラフの場合の依存関係の問題）が必要な場合、トポロジカルソート。 dfs を実行してリストを維持し、リストの先頭にノードの追加を開始します。すでにアクセスしたノードに遭遇した場合。次に、特定のグラフでサイクルを見つけました。

グラフがこのプロパティを満たす場合

|e| > |v| - 1

その後、グラフには少なくともオンサイクルが含まれます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top