3

無向グラフが与えられた場合、それがサイクルを含むかどうかを検出するための最良のアルゴリズムは何ですか？

訪問したノードを追跡しながら幅優先または深さ優先探索を行う方法の1つですが、これはO（n ^ 2）です。もっと速いものはありますか？

4

4 に答える 4

6

与えられたグラフ G(V,E) の BFS および DFS アルゴリズムの時間計算量は O(|V|+|E|) です。ご覧のとおり、入力の線形依存性です。非常に特殊なグラフがある場合は、いくつかのヒューリスティックを実行できますが、一般に、そのために DFS を使用することはそれほど悪くありません。ここでいくつかの情報を確認できます。とにかく、グラフ全体をトラバースする必要があります。

于 2009-05-14T10:31:25.200 に答える
4

O(V)アルゴリズムは次のとおりです。

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

... は DFS で実行できます。およびエッジが意味のある方法で (リストとして) 保存されている場合E<Vは、おそらく O(E)+logs を実行して、アルゴリズム全体を作成できますO(min(E,V))+logs。

少し遅れますが、この回答が気に入っていただければ幸いです。

于 2009-06-12T10:00:52.990 に答える
1

グラフが隣接リストを使用して表されている場合、深さ優先探索を使用してグラフG（V、E）にサイクルが存在するかどうかをテストするのはO（| V |、| E |）です。

サイクルがないことを示すには、グラフ全体をトラバースする必要があります。単にサイクルの有無に関心がある場合は、サイクルが検出された時点で明らかに終了できます。

于 2009-05-14T10:52:14.527 に答える
0

単純なグラフがある場合は、循環数を計算できます。

C = E − N + P

ここで、C はサイクル数、E はエッジ数、N はノード数、P はコンポーネント数です。グラフが接続されている場合、次のようになります。

C = E - N + 1
于 2012-05-01T07:22:37.597 に答える