请注意，图表示为邻接列表。
我听说过在图中找到循环的两种方法：
保留一个布尔值数组以跟踪您之前是否访问过某个节点。如果你用完了新的节点（没有碰到你已经去过的节点），那么只需回溯并尝试不同的分支。
来自 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;
}
}