注意，图形表示为邻接列表。
我听说过有两种方法可以在图中找到循环：
保留一个布尔值数组来跟踪您以前是否访问过节点。 如果您用尽了要去的新节点（没有命中已经访问过的节点），则回溯并尝试不同的分支。
来自Cormen的CLRS或Skiena的方法：对于未定向图中的深度优先搜索，有两种类型的边缘，树形和反向。当且仅当存在反向边时，图形才具有循环。
有人能够解释一下图的反向边是什么，以及上述两种方法之间的区别吗？谢谢。
更新：下面是检测这两种情况下循环的代码。 Graph是一个简单的类，用于将所有图形节点表示为唯一数字以简化，每个节点都有其相邻的邻居节点（g.getAdjacentNodes（int））：
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;
}
}
用 Java 编写来检测无向图中循环的代码：
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;
}
}
}
}
检测有向图中循环的Java代码：
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;
}
}
DFSCycle中检查循环的条件是不正确的。应该是if(i != u) // 如果相邻节点被访问且不是当前顶点的父节点，则存在一个循环。 { hasCycle = true; return; }- akhil_mittal} else if (v != u) {应该改为} else if (w != u) {，对吗？ - Etherealone