使用DFS检测图中的周期：2种不同的方法，有什么不同 [英] Detecting cycles in a graph using DFS: 2 different approaches and what's the difference
问题描述
我听说有两种方法可以在图表中找到一个循环：
-
保留一组布尔值来跟踪您之前是否访问过节点。如果你用完了新的节点（无需击中已经存在的节点），那么只需回溯并尝试其他分支即可。
来自Cormen的CLRS或Skiena：对于无向图中的深度优先搜索，有两种类型的边缘，即树和背面。这个图有一个循环，当且仅当存在一个后沿。
有人可以解释什么是后沿的图表，以及上述两种方法之间的区别。
谢谢。
更新：
这是两种情况下检测周期的代码。图是一个简单的类，它为了简单起见将所有的图节点表示为唯一的数字，每个节点都有它的相邻节点（g.getAdjacentNodes（int））：
public class Graph {
private int [] [] nodes; //所有节点;例如int [] [] nodes = {{1,2,3}，{3,2,1,5,6} ...};
public int [] getAdjacentNodes（int v）{
return nodes [v];
//图中顶点的数量
public int vSize（）{
return nodes.length;
}
}
检测Java代码在无向图中循环：
public class DFSCycle {
private boolean marked [ ]。
private int s;
私人图形g;
private boolean hasCycle;
// s - 起始节点
public DFSCycle（Graph g，int s）{
this.g = g;
this.s = s;
marked = new boolean [g.vSize（）];
findCycle（g，s，s）;
}
public boolean hasCycle（）{
return hasCycle;
public void findCycle（Graph g，int v，int u）{
marked [v] = true;
for（int w：g.getAdjacentNodes（v））{
if（！marked [w]）{
marked [w] = true;
findCycle（g，w，v）;
} else if（v！= u）{
hasCycle = true;
return;
}
}
}
}
用于检测有向图中的周期的Java代码：
public class DFSDirectedCycle {
私有布尔标记[];
private boolean onStack [];
private int s;
私人图形g;
private boolean hasCycle;
public DFSDirectedCycle（图g，int s）{
this.s = s
this.g = g;
marked = new boolean [g.vSize（）];
onStack = new boolean [g.vSize（）];
findCycle（g，s）;
}
public boolean hasCycle（）{
return hasCycle;
public void findCycle（Graph g，int v）{
marked [v] = true;
onStack [v] = true;
for（int w：g.adjacentNodes（v））{
if（！marked [w]）{
findCycle（g，w）;
} else if（onStack [w]）{
hasCycle = true;
return;
}
}
onStack [v] = false;
}
}
回答我的问题：
当且仅当存在后沿时，图形才有循环。后边是从节点到它自己的边（自循环），或者是由DFS生成的一个循环中的树的一个祖先。
意思是一样的。但是，此方法仅适用于无向图。
该算法对于有向图不起作用的原因是在有向图2中，到同一个顶点的不同路径不会形成一个循环。例如：A - > B，B - > C，A - > C - 不会形成循环，而在无向的循环中：A - B，B - C，C - p>
在无向图中查找循环
无向图有循环如果深度优先搜索（DFS）找到指向已经访问过的顶点（后沿）的边。
在有向图中查找循环 除了访问的顶点之外，我们还需要跟踪DFS遍历函数的递归堆栈中当前的顶点。如果我们到达一个已经在递归栈中的顶点，那么树中就有一个循环。 更新： Note that a graph is represented as an adjacency list. I've heard of 2 approaches to find a cycle in a graph: Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch. The one from Cormen's CLRS or Skiena: For depth-first search in undirected graphs, there are two types of edges, tree and back. The graph has a cycle if and only if there exists a back edge. Can somebody explain what are the back edges of a graph and what's the diffirence between the above 2 methods. Thanks. Update:
Here's the code to detect cycles in both cases. Graph is a simple class that represents all graph-nodes as unique numbers for simplicity, each node has its adjacent neighboring nodes (g.getAdjacentNodes(int)): Java code to detect cycles in an undirected graph: Java code to detect cycles in a directed graph:
Answering my question: The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle. Both approaches above actually mean the same. However, this method can be applied only to undirected graphs. The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does. Find a cycle in undirected graphs An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). Find a cycle in directed graphs In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. Update:
Working code is in the question section above. 这篇关于使用DFS检测图中的周期：2种不同的方法，有什么不同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
工作代码位于上述问题部分。
public class Graph {
private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
public int[] getAdjacentNodes(int v) {
return nodes[v];
}
// number of vertices in a graph
public int vSize() {
return nodes.length;
}
}
public class DFSCycle {
private boolean marked[];
private int s;
private Graph g;
private boolean hasCycle;
// s - starting node
public DFSCycle(Graph g, int s) {
this.g = g;
this.s = s;
marked = new boolean[g.vSize()];
findCycle(g,s,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v, int u) {
marked[v] = true;
for (int w : g.getAdjacentNodes(v)) {
if(!marked[w]) {
marked[w] = true;
findCycle(g,w,v);
} else if (v != u) {
hasCycle = true;
return;
}
}
}
}
public class DFSDirectedCycle {
private boolean marked[];
private boolean onStack[];
private int s;
private Graph g;
private boolean hasCycle;
public DFSDirectedCycle(Graph g, int s) {
this.s = s
this.g = g;
marked = new boolean[g.vSize()];
onStack = new boolean[g.vSize()];
findCycle(g,s);
}
public boolean hasCycle() {
return hasCycle;
}
public void findCycle(Graph g, int v) {
marked[v] = true;
onStack[v] = true;
for (int w : g.adjacentNodes(v)) {
if(!marked[w]) {
findCycle(g,w);
} else if (onStack[w]) {
hasCycle = true;
return;
}
}
onStack[v] = false;
}
}
