对于 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;
}
本文链接:https://www.f2er.com/1171907.html