在无向图中检测循环的方法逻辑

Question

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

同时，在查找解决方案以交叉检查我的逻辑时，我遇到了 this solution，它表示在执行 dfs 以及跟踪访问的节点时，您还需要跟踪递归中的节点堆栈并且是一个节点已经在递归堆栈中然后有一个循环 - 我不明白。
为什么我们需要跟踪递归堆栈中的节点，我们可以简单地检查一个节点是否再次访问并得出循环？

Answer 1

对于 undirected 图，使用 DFS 检测环很容易。 Back-edge 只不过是当前节点和它的祖先之间的边，它不是直接的 parent。因此，对于图中的循环，作为循环一部分的节点必须连接到它的祖先。这样，问题就简化为在图中找到 back-edge。在 undirected 图上应用 DFS 时，我们需要跟踪当前节点的 parent。起始节点没有parent，所以我们在DFS中传递parent = -1。我们在 child 上再次调用 DFS 并将其 parent 作为当前节点。现在我们检查当前节点的访问child是否是parent。如果 visited child 是 parent 那么没问题，因为它不是它的祖先，我们移动到它的下一个 child。但是如果 visited child 不是 parent 那么这个访问过的 child 必须是它的祖先，因此我们得到了 back-edge。一旦我们找到 back-edge，我们就会停止进一步 DFS 和 return 通知 'a cycle is present'。如果即使访问了所有节点也找不到 back-edge，则图中不存在循环。

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

Answer 2

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

后边是当前节点和它的祖先节点之间的边，而不是它的父节点。所以，为了在图中有一个循环，作为循环一部分的节点必须连接到它的祖先。在无向图上应用 DFS 时，我们需要跟踪当前节点的父节点。对于节点的每个邻居，如果访问了邻居而不是节点的父节点，那么我们就找到了循环。如果访问了该节点并且它是该节点的父节点，那么我们将继续处理下一个节点。如果我们之前没有访问过邻居，那么我们为这个邻居调用 DFS。我们需要添加条件

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

对于节点只有一个邻居且该邻居是其父节点的极端情况。然后，没有这个条件，只返回 return is_cyclic(n, node, graph, visited)) 我们跳过前一个节点的其余邻居。

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

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

在无向图中检测循环的方法逻辑

logic for method to detect cycle in an undirected graph

graph

depth-first-search

undirected-graph

cyclic-graph