66

n個の頂点 (| V | = n ) を持つ無向グラフG =( V , E ) が与えられた場合、 O ( n )にサイクルが含まれているかどうかをどのように確認しますか?

4

17 に答える 17

69

深さ優先探索で解決すると思います。探索されていないエッジが以前にアクセスしたノードにつながる場合、グラフにはサイクルが含まれます。この条件は、O(n) にもなります。これを true に設定したり、未探索のエッジを残さずに、最大 n 個のエッジを探索できるためです。

于 2009-02-08T21:00:32.940 に答える
34

実際、深さ優先（または実際には幅優先）検索では十分ではありません。見た目がより複雑なアルゴリズムが必要です。

たとえば、ノード{a、b、c、d}とエッジ{（a、b）、（b、c）、（b、d）、（d、c）}のグラフがあり、エッジ（x 、y）はxからyへのエッジです。（すべてのエッジが下向きになっている、このようなものに見えます。）

    (a)
     |
     |
    (b)
    / \ 
  (d)  |
   |   |
    \ /
    (c)

次に、深さ優先探索を実行すると、ノード（a）、次に（b）、次に（c）にアクセスし、次に（b）に戻り、次に（d）にアクセスし、最後に（c）に再度アクセスして、サイクルがあると結論付けることができます-ないとき。同様のことが幅優先で起こります。

あなたがする必要があるのは、訪問の途中でどのノードを追跡するかです。上記の例では、アルゴリズムが（d）に達すると、（c）の訪問は終了しますが、（a）または（b）は終了しません。したがって、完成したノードに再度アクセスすることは問題ありませんが、未完成のノードにアクセスすることは、サイクルがあることを意味します。これを行う通常の方法は、各ノードを白（まだ訪問していない）、灰色（子孫を訪問している）、または黒（訪問を終了している）に色付けすることです。

ここにいくつかの擬似コードがあります！

define visit(node n):
  if n.colour == grey: //if we're still visiting this node or its descendants
    throw exception("Cycle found")

  n.colour = grey //to indicate this node is being visited
  for node child in n.children():
    if child.colour == white: //if the child is unexplored
      visit(child)

  n.colour = black //to show we're done visiting this node
  return

次に、visit（root_node）を実行すると、サイクルがある場合にのみ例外がスローされます（最初はすべてのノードが白である必要があります）。

于 2009-02-10T16:07:18.627 に答える
16

循環を持たない接続された無向グラフ G は木です! 任意の木には正確に n − 1 個のエッジがあるため、グラフのエッジ リストを単純に走査してエッジを数えることができます。n − 1 個のエッジをカウントすると「yes」を返しますが、n 番目のエッジに到達すると「no」を返します。最大で n 個のエッジを調べるため、これには O (n) 時間かかります。

ただし、グラフが接続されていない場合は、DFS を使用する必要があります。エッジをトラバースすることができ、探索されていないエッジが訪問した頂点につながる場合、それには循環があります。

于 2016-01-04T17:58:33.300 に答える
6

ところで、それが接続されていることをたまたま知っている場合、単純にそれは木です (したがって循環はありません) |E|=|V|-1。もちろん、それは少量の情報ではありません:)

于 2011-11-21T17:10:39.727 に答える
4

答えは、実際には、幅優先検索です (または深さ優先検索、それは実際には問題ではありません)。詳細は分析にあります。

さて、アルゴリズムはどれくらい速いですか？

まず、グラフにサイクルがないことを想像してください。エッジの数は O(V) であり、グラフは森であり、目標は達成されました。

ここで、グラフにサイクルがあり、検索アルゴリズムが終了し、最初のサイクルで成功を報告するとします。グラフは無向であるため、アルゴリズムがエッジを検査するとき、可能性は 2 つしかありません。つまり、エッジのもう一方の端に到達したか、到達した後にこのエッジが円を閉じます。そして、エッジの他の頂点を確認すると、その頂点が「検査」されるため、これらの操作は O(V) しかありません。2 番目のケースは、アルゴリズムの実行中に 1 回だけ到達します。

于 2009-02-08T21:06:04.157 に答える
2

単純な DFS は、指定された無向グラフにサイクルがあるかどうかを確認する作業を行います。

これは同じC++コードです。

上記のコードで使用されているアイデアは次のとおりです。

すでに発見/訪問されたノードが再び発見され、それが親ノードではない場合、サイクルが発生します。

これは、以下のように説明することもできます (@Rafał Dowgird が言及)

探索されていないエッジが以前にアクセスしたノードにつながる場合、グラフにはサイクルが含まれます。

于 2015-06-26T19:26:31.773 に答える
2

条件付きの DFS アプローチ (親 != 次のノード) コードを見て、何が起こっているのかを理解しましょう。

bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 

    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 

        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
}

上記のコードはそれ自体を説明していますが、1 つの条件、つまり *i != 親を説明しようと思います。

1--2

次に、1 で 2 に移動すると、2 の親が 1 になり、1 に戻ると、1 は 2 の adj マトリックスにあるため、次の頂点 1 も 2 の親であるため、サイクルは検出されません。この DFS アプローチの直接の親。したがって、コードは正常に動作します

于 2019-11-05T07:05:01.567 に答える
1

DFS がバック エッジを生成しない場合、無向グラフは非循環 (つまり、フォレスト) です。バック エッジは、頂点を深さ優先ツリーの祖先 uに接続するエッジ ( したがって、単純に DFS を実行できます。バックエッジを見つけると、サイクルがあります。複雑さはではなく. バック エッジがある場合、明確なエッジが表示される前にバック エッジを検出する必要があるためです。これは、非循環 (無向) フォレストでは、.vuvO(V)O(E + V)|V||E| ≤ |V| + 1

于 2015-12-16T05:55:08.117 に答える
1

グラフが接続されているという仮定は一握りだと思います。したがって、実行時間が O(|V|) であるという上記の証明を使用できます。そうでない場合は、|E|>|V| です。注意: DFS の実行時間はO(|V|+|E|)です。

于 2010-01-19T23:32:43.610 に答える
0

DFS を正しく使用することは、コード内でグラフをどのように表現するかにも依存すると思います。たとえば、隣接ノードを追跡するために隣接リストを使用していて、グラフに 2 つの頂点と 1 つのエッジしかないとします: V={1,2} および E={(1,2)}。この場合、頂点 1 から開始して、DFS はそれを VISITED としてマークし、2 をキューに入れます。その後、頂点 2 がポップされます。1 は 2 に隣接しており、1 は VISITED であるため、DFS はサイクルがあると判断します (これは誤りです)。つまり、無向グラフ (1,2) と (2,1) は同じエッジであり、DFS がそれらを異なるエッジと見なさないようにコーディングする必要があります。訪問した各ノードの親ノードを保持すると、この状況を処理するのに役立ちます。

于 2014-02-28T10:16:53.487 に答える
0

これは、グラフに時間のサイクルがあるかどうかをチェックするアルゴリズムの C++ での簡単な実装ですO(n)(n はグラフ内の頂点の数です)。ここでは、Graph データ構造の実装は示しません (回答を簡潔にするため)。アルゴリズムは、Graph クラスに、 vector<int> getAdj(int v)隣接する頂点を返しv、int getV()頂点の総数を返す public メソッドがあることを想定しています。さらに、アルゴリズムは、グラフの頂点が から番号付けされていることを前提としてい0 to n - 1ます。

class CheckCycleUndirectedGraph
{
private:
    bool cyclic;
    vector<bool> visited;

    void depthFirstSearch(const Graph& g, int v, int u) {
        visited[v] = true;
        for (auto w : g.getAdj(v)) {
            if (!visited[w]) {
                depthFirstSearch(g, w, v);
            }
            else if (w != u) {
                cyclic = true;
                return;
            }
        }
    }

public:
    CheckCycleUndirectedGraph(const Graph& g) : cyclic(false) {
        visited = vector<bool>(g.getV(), false);
        for (int v = 0; v < g.getV(); v++) {
            if (!visited[v]){
                depthFirstSearch(g, v, v);
                if(cyclic)
                  break;
            }
        }
    }

    bool containsCycle() const {
        return cyclic;
    }
};

グラフはいくつかの接続されていないコンポーネントで構成されている場合があり、コンポーネント内にサイクルが存在する場合があることに注意してください。示されたアルゴリズムは、そのようなグラフでもサイクルを検出します。

于 2020-05-19T20:29:26.650 に答える
-2

循環のない無向グラフには |E| があります。< |V|-1。

public boolean hasCycle(Graph g) {

   int totalEdges = 0;
   for(Vertex v : g.getVertices()) {
     totalEdges += v.getNeighbors().size();
   }
   return totalEdges/2 > g.getVertices().size - 1;

}
于 2012-07-16T18:30:02.307 に答える