无向图中圈检测方法的逻辑

Question

我试图在有向图中检测一个循环
在提出解决该问题的逻辑时，我发现一个简单的图遍历等式dfs就足够了，因为在执行dfs时，我们可以有一个条件来查看是否已经访问了任何节点。如果是这样，就必须有一个循环

在查找交叉检查逻辑的解决方案时，我遇到了这样一个解决方案，即在执行dfs的同时跟踪访问的节点，您还需要跟踪递归堆栈中的节点，如果一个节点已经在递归堆栈中，那么就有一个循环-我不理解
当我们可以简单地检查是否再次访问某个节点并得出存在循环的结论时，为什么我们需要跟踪递归堆栈中的节点？

Answer 1

使用DFS，我们可以检测无向图。我们使用访问列表来检查节点是否已被访问，并且父节点从上一个方法的调用中标识节点的父节点。

Back edge是当前节点与其祖先（而不是其父节点）之间的边。因此，为了在图中有一个循环，作为循环一部分的节点必须连接到其祖先。在无向图上应用DFS时，我们需要跟踪当前节点的父节点。对于节点的每个邻居，如果访问的是邻居而不是节点的父节点，则我们找到了循环。如果访问了该节点，并且它是该节点的父节点，则我们继续下一个节点。如果我们之前没有访问过该邻居，那么我们将为该邻居调用DFS。我们需要增加条件

if(is_cyclic(n, node, graph, visited)):
    return True

对于节点只有一个邻居且该邻居是其父节点的角点情况。然后，在没有这个条件的情况下，通过返回return is_cyclic（n，node，graph，visted））我们跳过前一个节点的其余邻居。

对于第一个节点，我们作为父节点传递一个不属于图的节点。

def is_cyclic(node, parent, graph, visited):
    visited[node] = True
    for n in graph.neighbors(node):
        if visited[n]:
            if n != parent:
                return True
        else:
             if(is_cyclic(n, node, graph, visited)):
                 return True
    return False

Answer 2

对于无向图，使用DFS可以很容易地检测循环。因此，对于图中的循环，作为循环一部分的节点必须连接到它的祖先。这样，问题就减少到在图中找到后缘。当在无向图上应用DFS时，我们需要跟踪当前节点的父节点。没有起始节点的父节点，所以我们在DFS中传递它的父节点=-1。我们在子节点上再次调用DFS，它的父节点作为当前节点。现在我们检查当前节点的访问子节点是否是它的父节点。如果访问的子节点是它的父节点，那么没有问题，因为它不是它的祖先，我们移动到它的下一个子节点。但是如果访问的子节点不是它的父节点，那么这个访问的子节点必须是它的祖先，因此我们得到了一个后缘。一旦我们找到后缘，我们将停止进一步的DFS并返回通知存在循环。如果即使访问了所有节点，我们也没有找到后缘，那么循环在图中不存在。

bool dfs(int node,int parent,vector<vector<int>>&graph,vector<bool>&visited){
        visited[node]=true;
        for(int child: graph[node]){
                if(visited[child]==true){
                        if(child!=parent){ //backedge
                                return true;
                        }
                }
                else
                        return dfs(child,node,graph,visited);

        }
        return false;
}