如何使用递归 DFS 查找图形是否包含循环？

Question

下面的代码是深度优先的实现搜索 DFS 以确定有向图是否有环。但是，它似乎有一个错误，因为它不起作用。我几乎 100% 确定该错误位于 if (visited[w]) 条件下。我的逻辑基本上是——如果一个节点已经被访问过，那么一个循环就存在了。然而，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

你是正确的，没有办法判断被访问的节点是否已经被访问过或者是否作为当前遍历的一部分被访问过。

一种方法是维护一个顶点数组，该数组可以包含三个状态，而不是我们已经拥有的两个。

WHITE : Vertex is not processed yet. Initially all vertices are WHITE.

GRAY : Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (ind DFS tree) of this vertex are not processed yet (or this vertex is in function call stack)

BLACK : Vertex and all its descendants are processed.

While doing DFS, if we encounter an edge from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle.

代码将是这样的。

// 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

如何使用递归 DFS 查找图形是否包含循环？

How to find if a graph contains a cycle using a recursive DFS?

c

algorithm

graph-theory