如何查找圖形是否包含使用遞歸DFS的循環？

下面的代碼是深度優先的搜索DFS的實現，以確定有向圖是否有循環或不循環。但是，它似乎有一個錯誤，因爲它不工作。我幾乎100％肯定該錯誤在於if (visited[w])的條件。我的邏輯基本上是 - 如果一個節點已經被訪問過，那麼就存在一個循環。然而，if (visited[w])的問題在於，儘管條件可能是真實的，但並不一定意味着存在週期，因爲該節點可能早已被訪問過。如何查找圖形是否包含使用遞歸DFS的循環？

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 
}

來源

2017-10-19 novice

'的malloc（）'不初始化它提供給你的內存，你不自己初始化。誰知道它裏面有什麼？如果你希望它以全零開始，那麼最簡單的解決方案是使用'calloc（）'而不是'malloc（）'進行分配。 –

@JohnBollinger我使用for循環（以上未顯示）將所有內容初始化爲0，但這顯然不是問題 – novice

另外，您從節點0開始執行DFS，但如果圖形未連接，則可能會錯過一個循環無法從該節點訪問。 –

你是正確的，也沒有辦法，如果訪問的節點已經被訪問或者訪問被作爲當前遍歷的一部分，告訴。

一種方法是維護可以容納三個狀態而不是我們已有的兩個狀態的頂點數組。

白色：頂點尚未處理。最初所有的頂點都是白色的。

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; 
}

這裏的主要區別在於，一個節點可以訪問並且仍然爲黑色（指示節點較早訪問）或灰色（指示該節點被訪問的作爲當前遍歷的一部分;所以這是一個後端）幫助我們找出我們是否有一個循環。

由於布爾數組，我們以前不可能做到這一點，因爲我們沒有區分兩種訪問節點。

Source

來源

2017-10-20 00:07:28 thebenman

如何查找圖形是否包含使用遞歸DFS的循環？

回答

相關問題