無向圖環(huán)的判斷

• 并查集判斷
  • 如果兩個結(jié)點父親相同，并且兩個結(jié)點之間有邊相連，則存在環(huán)

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的過程中如果遇到已經(jīng)訪問過的點，并且這個點不是自己的直接父親，那么就必然存在環(huán)

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]) {//默認第一個結(jié)點沒有父節(jié)點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;}

有向圖環(huán)的判斷

• 單純判斷
  • 在dfs的過程中，把dfs經(jīng)過的結(jié)點全部保存在一個棧上（或者直接用布爾數(shù)組進行標記），然后每當經(jīng)過一個結(jié)點時，判斷當前結(jié)點是否在棧上，是則有環(huán)
  • 事實上其實質(zhì)就是，在dfs的過程中又遇到了已經(jīng)訪問過的點，則必然存在環(huán)
• 問題：為什么這里不需要考慮：如果該點已經(jīng)被訪問過并且該點是父親結(jié)點的情況呢？無向圖中不是考慮了嗎？
  • 這里是有向圖，如果從孩子結(jié)點能有邊返回到父親結(jié)點，那么顯然這兩者之間存在環(huán)。
• 記錄環(huán)中的結(jié)點
  • 需要用棧記錄當前路徑經(jīng)過的結(jié)點，并且記錄每個結(jié)點的父親結(jié)點，也就是說記錄一下在當前路徑中，當前結(jié)點是哪一個結(jié)點來的。
  • 如果遇到了一個結(jié)點已經(jīng)被訪問過并且在棧上， 那么必然存在一個有向環(huán)。從這個結(jié)點出發(fā)，一直找當前結(jié)點的父結(jié)點，記錄到結(jié)果容器里面，直到又遇到這個結(jié)點。
  • 注意這個dfs路徑記錄棧，當某一次dfs要返回的時候(此時已經(jīng)確定在 這一遍dfs中無法找到環(huán))，則沿途回溯取消所有結(jié)點在棧上的標記（把布爾數(shù)組置為false）

public class DiCycle {private boolean[] marked;//記錄結(jié)點是否訪問過private int[] edgeTo;//記錄該結(jié)點的父節(jié)點private Stack<Integer> cycle;private boolean[] onStack;//記錄當前訪問路徑上的結(jié)點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 stubmarked[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();}}

轉(zhuǎn)載于:https://www.cnblogs.com/czsharecode/p/10709715.html

總結(jié)

以上是生活随笔為你收集整理的图论中环的判断的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。