无向图环的判断
- 并查集判断
- 如果两个结点父亲相同，并且两个结点之间有边相连，则存在环
def init();
def find(int x);//必须进行路径压缩
def merge(int x, int y);
if(find(x) == find(y) && G[x][y] != 0){ cycle = true;}
else merge(x,y);
- DFS判断
- dfs的过程中如果遇到已经访问过的点，并且这个点不是自己的直接父亲，那么就必然存在环
public class Cycle {
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph G) {
this.marked = new boolean[G.V()];
this.hasCycle = false;
for(int i=1; i<G.V(); i++) {
if(!marked[i]) {
//默认第一个结点没有父节点
dfs(G, i, -1);
}
}
}
private void dfs(Graph G, int cur, int pre) {
marked[cur] = true;
for(Integer nxt : G.adj(cur)) {
if(!marked[nxt]) {
dfs(G, nxt, cur);
}
else if(nxt != pre) {
this.hasCycle = true;
}
}
}
public boolean hasCycle() {return this.hasCycle;}
有向图环的判断
-
单纯判断
- 在dfs的过程中，把dfs经过的结点全部保存在一个栈上（或者直接用布尔数组进行标记），然后每当经过一个结点时，判断当前结点是否在栈上，是则有环
- 事实上其实质就是，在dfs的过程中又遇到了已经访问过的点，则必然存在环
-
问题：为什么这里不需要考虑：如果该点已经被访问过并且该点是父亲结点的情况呢？无向图中不是考虑了吗？
- 这里是有向图，如果从孩子结点能有边返回到父亲结点，那么显然这两者之间存在环。
-
记录环中的结点
- 需要用栈记录当前路径经过的结点，并且记录每个结点的父亲结点，也就是说记录一下在当前路径中，当前结点是哪一个结点来的。
- 如果遇到了一个结点已经被访问过并且在栈上， 那么必然存在一个有向环。从这个结点出发，一直找当前结点的父结点，记录到结果容器里面，直到又遇到这个结点。
- 注意这个dfs路径记录栈，当某一次dfs要返回的时候(此时已经确定在 这一遍dfs中无法找到环)，则沿途回溯取消所有结点在栈上的标记（把布尔数组置为false）
public class DiCycle {
private boolean[] marked;//记录结点是否访问过
private int[] edgeTo;//记录该结点的父节点
private Stack<Integer> cycle;
private boolean[] onStack;//记录当前访问路径上的结点
public DiCycle(Digraph G) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
cycle = new Stack<Integer>();
onStack = new boolean[G.V()];
for(int i=0; i<G.V(); i++) {
if(!marked[i]) {
dfs(G, i);
}
}
}
private void dfs(Digraph G, int v) {
// TODO Auto-generated method stub
marked[v] = true;
onStack[v] = true;
for(Integer w : G.adj(v)) {
if(this.hasCycle()) return ;
else if(!marked[w]) {
edgeTo[w] = v;
dfs(G , w);
}
else if(onStack[w]) {
for(int x=v; x!=w; x=edgeTo[x]) {
cycle.push(x);
}
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;//回溯时取消其在栈上，相当于清空栈，便于下一次dfs
}
public void showCycle() {
if(!this.hasCycle()) System.out.println("no cycle...");
Stack<Integer> s = new Stack<Integer>();
s = (Stack<Integer>) cycle.clone();
while(!s.isEmpty()) {
System.out.println(s.peek());
s.pop();
}
}