摘要:不在的話,表示不構成環,我們應該合并這兩個集合因為加上這條邊,兩個集合就被連起來了,合并成了一個集合注意如果想要復雜度為必須用路徑壓縮。并查集寫法參考注意方法用找的老大哥,合并的是的老大哥。
Detect Cycle in Directed Graph 有向圖找環
黑白灰DFS大法 復雜度Given n nodes labeled from 0 to n - 1 and a list of directed edges (each edge is a pair of nodes), write a function to check whether the graph contains a cycle. if edges = [0, 1], [1, 2], [0, 2]], it means 0 -> 1, 1 ->2, 0 -> 2. edges[i is parent, edgesi is child.
For example:
Given n = 3 and edges = [[0, 1], [1, 2], [0, 2], return true.
Given n = 3 and edges = [[0, 1], [1, 2], [2, 0], return false.
O( V + E ) 時間 O(V) 空間
思路什么是有向圖有環:只要從a可以到a,經過的邊的個數大于等于1
做法:
維護三個點的集合:
白點集合,里面放還沒explore的點
灰點集合,里面放正在explore的點,當前的灰點們表示一條正在explore的路徑,這個路徑上的每個點都是灰的
黑點集合,里面放已經explore的點且這些點不構成環
如果我將要的訪問的點是黑點,我是否需要訪問他?
答:不需要,一個點是黑的表示這個點的所有孩子(鄰居)都explore過了,且沒發現環,且這個點的所有孩子必定也全是黑的。
何時把一個點由灰變黑?
答:當這個點的所有孩子都訪問完(都已變黑)了且沒有發現環
如果我將要訪問的點是個灰點,說明什么?
答:發現了環。假設explore到了cur點,cur點為灰色,此時所有其他的灰色點必定都是我的祖先,因為他們都是當前explore的路徑上的點,cur在最戰線的最前方explore,如果cur點在explore的時候發現自己的的孩子(鄰居)有一個灰色,表示下面這個點即是我的祖先也是我的孩子,說明從cur可以走到cur自己,即出現了環。
無向圖和有向圖很不一樣,不是一回事
代碼核心代碼:
public boolean hasCycleDirectedGraph(int n, int[][] edges) {//前指后 HashSetblack = new HashSet (); HashSet white = new HashSet (); HashSet gray = new HashSet (); List > adjList = new ArrayList
>(); for (int i = 0; i < n; ++i) { white.add(new Integer(i)); adjList.add(new ArrayList
()); } for (int[] edge: edges) { adjList.get(edge[0]).add(new Integer(edge[1])); } for (int i = 0; i < n; i++) { if (white.contains(i)) { if (hasCycle(i, white, gray, black, adjList)) return true; } } return false; } private boolean hasCycle(Integer vertex, HashSet white, HashSet gray, HashSet black, List > adjList) { white.remove(vertex); gray.add(vertex); // current vertex is being visited for (Integer succ: adjList.get(vertex)) { // successors of current vertex if (white.contains(succ)) { if (hasCycle(succ, white, gray, black, adjList)) return true; } else if (gray.contains(succ)) { return true; } else if (black.contains(succ)) { continue; } } gray.remove(vertex); black.add(vertex); return false; }
測試代碼:
public class Solution { public static void main(String[] args) { Solution so = new Solution(); int[][] edges = {{0, 1}, {1, 2}, {2, 0}}; boolean result = so.hasCycleDirectedGraph(3, edges); System.out.println(result); } }Detect Cycle in Undirected Graph 無向圖找環
并查集大法 復雜度Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether the graph contains a cycle.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return false.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return true.
O( V + E ) 時間 O(V) 空間
思路什么是無向圖有環:只要從a可以到a,路徑中每個邊只用一次
數據結構:
并查集:
規定集合(即一個連通分量)應該滿足的property:里面的任意兩點有且只有一條路徑可達。
最開始的時候n個點有n個連通分量,即n個集合。
做法:
想象一開始這個圖只有頂點,沒有邊,我們來一條一條的添加邊。
每遇到一條邊,判斷這邊的兩個端點是否在同一個集合里?
在的話,表示有環:因為兩個點在一個集合里就表示這兩個點已經有一條路徑了,現在再加一條路徑,必然構成環。
不在的話,表示不構成環,我們應該合并這兩個集合:因為加上這條邊,兩個集合就被連起來了,合并成了一個集合
注意如果想要復雜度為O(V+E),必須用路徑壓縮。
并查集寫法參考
注意union(p,q)方法:用find()找p,q的老大哥,合并的是p,q的老大哥。
UnionFind Utility(非常intuitive,應該練習在5分鐘內寫完):
class UnionFind { private int[] father; private int count; public UnionFind(int n) { father = new int[n]; count = n; for (int i = 0; i < n; i++){ father[i] = i; } } public int count() { return this.count; } public int find(int p) { int root = father[p]; while (root != father[root]) root = father[root]; //as long as we get here, root is the final dad while (p != root) { int tmp = father[p]; father[p] = root; p = tmp; } return root; } public void union(int p, int q) { int fatherP = find(p); int fatherQ = find(q); if (fatherP != fatherQ) { father[fatherP] = fatherQ; count--; } } }
主程序
public class Solution { public boolean validTree(int n, int[][] edges) { UnionFind uf = new UnionFind(n); for (int[] edge : edges){ int p = edge[0]; int q = edge[1]; if (uf.find(p) == uf.find(q)) return false; else uf.union(p,q); } return uf.count() == 1; } }DFS/BFS法 復雜度
O( V + E ) 時間 O(V) 空間
思路無向圖找環和有向圖找環本質上完全不同。
有向圖找環需要三種顏色。
無向圖找環只需要兩種顏色,就是訪問過的和沒訪問的。
dfs過程中如果碰到訪問過的節點(當然這個節點不能是來時的節點),就是有環。
注意Integer的比較問題
代碼public class Solution { public boolean validTree(int n, int[][] edges) { HashSetvisited = new HashSet (); List > adjList = new ArrayList
>(); for (int i=0; i
()); for (int[] edge: edges) { adjList.get(edge[0]).add(edge[1]); adjList.get(edge[1]).add(edge[0]); } if (hasCycle(-1, 0, visited, adjList)) // has cycle? return false; if (visited.size() != n) // is all connected? return false; return true; } private boolean hasCycle(Integer pred, Integer vertex, HashSet visited, List > adjList) { visited.add(vertex); // current vertex is being visited for (Integer succ: adjList.get(vertex)) { // successors of current vertex if (!succ.equals(pred)) { // exclude current vertex"s predecessor if (visited.contains(succ)) { return true; // back edge/loop detected! } else { if (hasCycle(vertex, succ, visited, adjList)) { return true; } } } } return false; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64794.html
摘要:無向圖對于無向圖,需要記錄一個來判斷這是不是無向圖兩個之間的連接。同一層的節點會出現相連的情況。如果同一層的這個節點是等待訪問的,說明這兩個節點之間有連接,所以有環的出現。有向圖不需要記錄 Graph: Detect Cycle Detect if any cycle exists in the graph. 無向圖 0 - 1 | / 2 對于無向圖,需要記錄一個previous ...
摘要:邊僅由兩個頂點連接,并且沒有方向的圖稱為無向圖。用分隔符當前為空格,也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點,計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...
摘要:離心率計算題目釋義計算點的離心率,圖的直徑,半徑,中心計算圖的圍長定義點的離心率圖中任意一點,的離心率是圖中其他點到的所有最短路徑中最大值。圖的中心圖中離心率長度等于半徑的點。改動離心率計算,在遍歷中增加的賦值即可。 離心率計算 4.1.16 The eccentricity of a vertex v is the the length of the shortest path fr...
Graph: Topological Sort 利用和detect cycle類似的思路, 用dfs + recursion解決。并且一定時一個有向圖。 Stack stack = new Stack(); // 0:unvisit, 1:visited, 2:visiting public boolean topologicalSort(Node node) { if(node.stat...
摘要:感謝您的閱讀如果喜歡這篇文章請點贊。它對我意義重大,它能幫助其他人看到這篇文章。對于更高級的文章,你可以在或上跟隨我。 I’ve worked with Angular.js for a few years and despite the widespread criticism I think this is a fantastic framework. I’ve started w...
閱讀 2801·2023-04-25 22:51
閱讀 2026·2021-10-11 10:58
閱讀 3308·2019-08-30 10:49
閱讀 1870·2019-08-29 17:09
閱讀 3136·2019-08-29 10:55
閱讀 839·2019-08-26 10:34
閱讀 3467·2019-08-23 17:54
閱讀 980·2019-08-23 16:06