グラフ内のループを検出する最速のアルゴリズム

無向グラフを仮定すると、サイクルが含まれているかどうかを検出する最適なアルゴリズムは何ですか？グラフ内のループを検出する最速のアルゴリズム

幅優先又は深さ優先探索訪れたノードのトラックを維持しながらは、一つの方法であるが、それはO（N^2）です。何か速いですか？（| V | + | E |）与えられたグラフG（V、E）のため

2009-05-14 Frederick The Fool

BFSとDFSアルゴリズムがOの時間複雑性を有します。あなたが見ることができるように、入力の線形依存性です。非常に特化したグラフがある場合に備えて、ヒューリスティックを実行できますが、一般的にDFSを使用するのはそれほど悪くありません。いくつかの情報hereを確認することができます。とにかくグラフ全体を走査しなければなりません。グラフは、隣接リストを使用して表現されている場合（| V |、| | E）深さ優先探索を使用してグラフG（V、E）でサイクルが存在する

出典

2009-05-14 10:31:25

おかげで、私はすべて訪れたノードの集合は非常に小さい冒頭であり、唯一のアルゴリズムが進むにつれて成長しているという事実を無視して推測します。 –

テストはOです。

それにはサイクルが存在しない表示するグラフ全体を横断する必要があります。単にサイクルの有無に関心がある場合は、明らかにサイクルが発見された時点で終了することができます。

def hasCycles(G, V, E): 
    if E>=V: 
     return True 
    else: 
     # here E<V 
     # perform O(E+V) = O(V) algorithm 
     ...

... DFSで行うことができます。

出典

2009-05-14 10:52:14 mealnor

はここにあなたのO(V)アルゴリズムです。 E<Vがあり、エッジが意味のある方法で（リストとして）格納されている場合は、O（E）+ログを使用すると、アルゴリズム全体をO(min(E,V))+logsとすることができます。

少し遅くても、この回答が欲しいと思います！

出典

2009-06-12 10:00:52

ご覧のとおり、サイクルのない無向グラフはツリーの部分グラフなので、E

単純なグラフを持っている場合は、サイクロマティック数を計算することができる：Cはサイクル数である

C = E − N + P

、Eはエッジの数であるが、Nはノードの数であり、Pはコンポーネントの数。あなたが接続されているグラフならば、それは次のようになります。

C = E - N + 1

出典

2012-05-01 07:22:37 Moa

グラフ内のループを検出する最速のアルゴリズム

答えて

関連する問題