如何查找图形是否包含使用递归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的循环？

回答

相关问题