グラフに再帰DFSを使用したサイクルが含まれているかどうかを調べるにはどうすればよいですか？

Question

以下のコードは、有向グラフにサイクルがあるかどうかを判断するために、深さ優先の 検索DFSの実装です。しかし、動作していないので、そこにバグがあるようです。私はそのバグがif (visited[w])状態にあることをほぼ100％確信しています。ここでの私のロジックは、基本的には - ノードが既に訪問されている場合は、サイクルが存在します。しかし、if (visited[w])の問題は、条件が真であるかもしれないが、ノードがずっと前に訪れたかもしれないので、サイクルがあることを必ずしも意味しないということである。

int *visited; // array [0..V-1] of booleans 

int checkCycle(Graph g) 
{ 
    visited = malloc(sizeof(int)*g->numVertices); 
    int result = dfsCycleCheck(g, 0); 
    free(visited); 
    return result; 
} 
int dfsCycleCheck(Graph g, Vertex v) 
{ 
    visited[v] = 1; 
    Vertex w; 
    for (w = 0; w < nV(g); w++) { 
     if (!hasEdge(g,v,w)) continue; 
     if (visited[w]) return 1; // found cycle 
     return dfsCycleCheck(g, w); 
    } 
    return 0; // no cycle 
} 

Answer 1

あなたは訪問したノードがすでに訪問された場合、または現在のトラバーサルの一環として訪れたか伝える方法がないことを正しいです。

1つのアプローチは、既に持っている2つの状態の代わりに3つの状態を保持できる頂点の配列を維持することです。

ホワイト：頂点はまだ処理されていません。最初は すべての頂点は白です。

GRAY：頂点が処理されている（この 頂点のDFSは、この頂点 のすべての子孫（IND DFSツリーが）まだ処理（または、この頂点が機能 呼び出しであるされていないことを 意味し始めたが、終わっていませんスタック）

BLACK：頂点とそのすべての子孫が を処理している

DFSをやっている間、私たちは、 GRAY頂点に現在の頂点からエッジが発生した場合、このエッジはバックエッジであるので、そこにありますサイクル。

コードは次のようになります。

// Recursive function to find if there is back edge 
// in DFS subtree tree rooted with 'u' 
bool Graph::DFSUtil(int u, int color[]) 
{ 
    // GRAY : This vertex is being processed (DFS 
    //   for this vertex has started, but not 
    //   ended (or this vertex is in function 
    //   call stack) 
    color[u] = GRAY; 

    // Iterate through all adjacent vertices 
    list<int>::iterator i; 
    for (i = adj[u].begin(); i != adj[u].end(); ++i) 
    { 
     int v = *i; // An adjacent of u 

     // If there is 
     if (color[v] == GRAY) 
      return true; 

     // If v is not processed and there is a back 
     // edge in subtree rooted with v 
     if (color[v] == WHITE && DFSUtil(v, color)) 
      return true; 
    } 

    // Mark this vertex as processed 
    color[u] = BLACK; 

    return false; 
} 

// Returns true if there is a cycle in graph 
bool Graph::isCyclic() 
{ 
    // Initialize color of all vertices as WHITE 
    int *color = new int[V]; 
    for (int i = 0; i < V; i++) 
     color[i] = WHITE; 

    // Do a DFS traversal beginning with all 
    // vertices 
    for (int i = 0; i < V; i++) 
     if (color[i] == WHITE) 
      if (DFSUtil(i, color) == true) 
       return true; 

    return false; 
} 

ここでの主な違いは、（ノードが訪問し、依然としてブラック（ノードが以前に訪れたことを示す）またはグレーのいずれかとすることができることであるノードが現在のトラバースの一環として訪れたことを示します;それはバックエッジです）私たちがサイクルを持っているかどうかを知るのを助けます。

私たちが2種類の訪問先ノードを区別していなかったブール配列のため、以前は不可能でした。

Source