请注意，图表表示为邻接列表 .
我听说有两种方法可以在图表中找到一个循环：
-
保留一个布尔值数组，以跟踪您之前是否访问过某个节点 . 如果你的新节点用完了（没有点击你已经存在的节点），那么只需回溯并尝试不同的分支 .
-
来自Cormen的CLRS或Skiena的那个：对于无向图中的深度优先搜索，有两种类型的边，树和背面 . 当且仅当存在后沿时，图形具有循环 .
有人可以解释图形的后边缘是什么，以及上述两种方法之间的差异是什么 .
谢谢 .
Update: 这是两种情况下检测周期的代码 . 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 code to detect cycles in an undirected graph:
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 code to detect cycles in a directed graph:
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;
}
}
3 回答
Answering my question:
当且仅当存在后沿时，图形具有循环 . 后边缘是从节点到自身（自循环）的边缘或由DFS形成循环的树中的其祖先之一 .
上述两种方法实际上都是相同的 . 但是，此方法只能应用于 undirected graphs .
该算法不适用于有向图的原因在于，在有向图2中，到相同顶点的不同路径不形成循环 . 例如：A - > B，B - > C，A - > C - 不进行循环，而在无向循环中：A - B，B - C，C - A .
Find a cycle in undirected graphs
当且仅当深度优先搜索（DFS）找到指向已访问的顶点（后边缘）的边时，无向图具有循环 .
Find a cycle in directed graphs
除了访问顶点之外，我们还需要跟踪当前在DFS遍历的函数的递归堆栈中的顶点 . 如果我们到达已经在递归堆栈中的顶点，那么树中就有一个循环 .
Update: 工作代码在上面的问题部分 .
为了完成，可以使用DFS（来自wikipedia）在有向图中找到循环：
这是我用C编写的基于DFS的代码，用于确定给定的 undirected graph 是否连接/循环 . 最后有一些样本输出 . 希望它会有所帮助:)
Sample Output: