0

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

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

4

2 回答 2

1

对于undirected图，检测循环很容易使用DFS. Back-edge只不过是当前节点与其不是直接父节点的祖先节点之间的边缘。因此，对于图中的循环，作为循环一部分的节点必须连接到它的祖先。这样，问题就减少到在图中找到后边。DFS在图上应用时undirected，我们需要跟踪当前节点的父节点。起始节点没有父节点，所以我们将它传递给parent = -1. DFS我们DFS再次调用子节点，并将其父节点作为当前节点。现在我们检查当前节点的访问子节点是否是它的父节点。如果visited child是它的父母，那么没问题，因为它不是它的祖先，我们转移到它的下一个孩子。但如果visited child不是它的父母，那么这个被访问的孩子必须是它的祖先，因此我们得到了一个后边。一旦我们找到后沿，我们就会进一步停止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;
}
于 2021-02-06T06:02:29.990 回答
0

使用 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
于 2021-11-26T21:27:32.193 回答