algorithm - 使用 BFS 或 DFS 在有向图中查找循环

Question

我尝试浏览 Internet，但目前我对修改 BFS 或 DFS 算法以便能够在有向图中找到环路有点困惑。如果图不是有向的，DFS 算法会使用后向边来解决这个问题，但在查看有向图时这种方法会失败。

谁能指出我正确的方向？感谢您的宝贵时间。

Answer 1

跟踪当前在 DFS 遍历函数的递归堆栈中的顶点。如果你到达一个已经在递归堆栈中的顶点，那么树中就有一个循环。

创建一个数组 recStack[] 并添加其中访问的每个顶点。如果遇到一个已经访问过的顶点，则存在一个循环，您可以通过将该顶点再次传递给修改后的 DFS 函数进行打印来打印

bool isGraphCyclic(int v, bool visited[], bool *recStack)
{
    if(visited[v] == false)
    {
        // Mark the current node as visited and part of recursion stack
        visited[v] = true;
        recStack[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 ( !visited[*i] && isGraphCyclic(*i, visited, recStack) )
                return true;
            else if (recStack[*i])
                return true;
        }

    }
    recStack[v] = false;  // remove the vertex from recursion stack
    return false;
}