并查集
并查集思路：
- 有若干個樣本a，b，c，d...假設型別都是V
- 在并查集中一開始認為每個樣本都在單獨的集合里
- 用戶可以在任何時候呼叫倆個方法：boolean isSameSet(V x,V y)：查詢樣本x和樣本y是否屬于一個集合；boolean union(V x,V y):把x和y各自所在的集合的所有樣本合并成一個集合，把小集合的頭節點直接連到大集合的頭節點上
- isSameSet和union的代價越低越好
圖解
代碼
方法：
UnionFind：初始化一個節點
findFather：找到某個節點的祖宗節點
isSameSet：判斷倆個節點是否在一個集合
union：倆個集合進行合并
public class Test { public static class Node<V> { V value; public Node(V v) { value = v; } } public static class UnionFind<V> { //V---->節點 public HashMap<V, Node<V>> nodes; //K某個節點--->value祖宗節點 public HashMap<Node<V>, Node<V>> parents; //K祖宗節點--->value以該節點為頭節點的集合的大小 public HashMap<Node<V>, Integer> sizeMap; //初始化程序：將所有樣本放在List<V> values V{a,b,c,d,e} --->{a}{b}{c}{d}{e} public UnionFind(List<V> values) { nodes = new HashMap<>(); parents = new HashMap<>(); sizeMap = new HashMap<>(); for (V cur : values) { //每個值做成一個node Node<V> node = new Node<>(cur); nodes.put(cur, node); parents.put(node, node); sizeMap.put(node, 1); } } //給你一個節點，找到祖宗節點，把組總結點回傳，重要優化把整個鏈打扁平 public Node<V> findFather(Node<V> cur) { Stack<Node<V>> path = new Stack<>(); //跳出這個while時cur就是祖宗節點 while (cur != parents.get(cur)) { path.push(cur); cur = parents.get(cur); } //cur祖宗節點，path里面存著沿途路徑的每個節點 while (!path.isEmpty()) { parents.put(path.pop(), cur); } return cur; } //如果a樣本跟b樣本的祖宗節點一樣就是一個集合 public boolean isSameSet(V a, V b) { return findFather(nodes.get(a)) == findFather(nodes.get(b)); } //將a集合與b集合合并 public void union(V a, V b) { Node<V> aHead = findFather(nodes.get(a)); Node<V> bHead = findFather(nodes.get(b)); if (aHead != bHead) { int aSetSize = sizeMap.get(aHead); int bSetSize = sizeMap.get(bHead); //big表示大集合的祖宗節點 Node<V> big = aSetSize >= bSetSize ? aHead : bHead; //small表示小集合的祖宗節點 Node<V> small = big == aHead ? bHead : aHead; parents.put(small, big); sizeMap.put(big, aSetSize + bSetSize); sizeMap.remove(small); } } public int sets() { return sizeMap.size(); } } }
舉栗子：
如果倆個user，a欄位一樣，或者b欄位一樣，或者c欄位一樣，就認為是一個人，
請合并users，回傳合并之后的用戶數量
圖解：
代碼：
public static class User{ public String a; public String b; public String c; public User(String a, String b, String c) { super(); this.a = a; this.b = b; this.c = c; } } //題目：如果倆個user，a欄位一樣，或者b欄位一樣，或者c欄位一樣，就認為是一個人 //請合并users，回傳合并之后的用戶數量 public static int mergeUsers(List<User> users) { UnionFind<User> unionFinds = new UnionFind(users); HashMap<String,User> mapA= new HashMap<>(); HashMap<String,User> mapB= new HashMap<>(); HashMap<String,User> mapC= new HashMap<>(); for(User user : users) {
//如果mapA中包含這個用戶的a欄位，則進行合并，不包含則添加到mapA中 if(mapA.containsKey(user.a)) { unionFinds.union(user, mapA.get(user.a)); }else { mapA.put(user.a, user); } if(mapB.containsKey(user.b)) { unionFinds.union(user, mapB.get(user.b)); }else { mapB.put(user.b, user); } if(mapC.containsKey(user.c)) { unionFinds.union(user, mapC.get(user.c)); }else { mapC.put(user.c, user); } } return unionFinds.getSetNum(); }
圖
基本介紹：
- 由點的集合和邊的集合構成
- 雖然存在有向圖和無向圖的概念，但實際上都可以用有向圖來表示
- 邊上帶有權值
圖結構的表達
圖結構的表達有很多種方式，例如鄰接表法，鄰接矩陣
所以可以找一種自己熟悉的結構，把題目中給的結構轉化為自己熟悉的結構：
代碼：
點結構的描述
// 點結構的描述 value: 編號 in：入度個數 out：出度個數 nexts：出度的直接鄰居 edges：邊結構 public class Node { public int value; public int in; public int out; public ArrayList<Node> nexts; public ArrayList<Edge> edges; public Node(int value) { this.value =https://www.cnblogs.com/thirtyFan/p/ value; in = 0; out = 0; nexts = new ArrayList<>(); edges = new ArrayList<>(); } }
邊結構描述
//weight：權重 from: 出發的點 to:到達的點 public class Edge { public int weight; public Node from; public Node to; public Edge(int weight, Node from, Node to) { this.weight = weight; this.from = from; this.to = to; } }
圖結構描述
public class Graph { //由點集與邊集構成 HashMap：key 編號 value：點結構 public HashMap<Integer, Node> nodes; public HashSet<Edge> edges; public Graph() { nodes = new HashMap<>(); edges = new HashSet<>(); } }
常見的圖結構有如下表達：
[[7,0,4] [4,1,3] [3,2,3] [8,2,4]] ------>[權值，from，to]
將這種結構轉化為自己上面我們所述的圖結構
代碼：
/* * N*3 的矩陣轉為為我們熟悉的圖結構程序 * [5,0,7] [3,0,1][weight,from節點上面的值，to節點上面的值] */ public static Graph createGraph(int[][] matrix) { Graph graph = new Graph(); for (int i = 0; i < matrix.length; i++) { // 拿到每一條邊， matrix[i] int weight = matrix[i][0]; int from = matrix[i][1]; int to = matrix[i][2]; //如果圖結構的點集沒有from這個點，在圖結構中的點集中添加 if (!graph.nodes.containsKey(from)) { graph.nodes.put(from, new Node(from)); } if (!graph.nodes.containsKey(to)) { graph.nodes.put(to, new Node(to)); } //可以拿到from編號所對應的點，to編號所對應的點，以及邊 Node fromNode = graph.nodes.get(from); Node toNode = graph.nodes.get(to); //這條邊從from點出發到to點 Edge newEdge = new Edge(weight, fromNode, toNode); //添加from點的直接鄰居 fromNode.nexts.add(toNode); fromNode.out++; toNode.in++; //將這條邊添加到from的直接邊的集合中 fromNode.edges.add(newEdge); graph.edges.add(newEdge); } return graph; }
圖的寬度優先遍歷（bfs）
基本思路
- 利用佇列實作
- 從源節點依次按照寬度進佇列，然后彈出
- 沒彈出一個節點，把該節點所有沒有進過佇列的鄰接點放入佇列
- 直到佇列變空
圖解
代碼
//從node出發，進行寬度優先遍歷，一層一層遍歷 //在二叉樹中bfs不用set，因為二叉樹沒有環的問題 public static void bfs(Node start) { if (start == null) { return; } Queue<Node> queue = new LinkedList<>(); HashSet<Node> set = new HashSet<>(); queue.add(start); set.add(start); while (!queue.isEmpty()) { //彈出列印 Node cur = queue.poll(); System.out.println(cur.value); //直接鄰居沒有進過set的加入set與queue，避免環 for (Node next : cur.nexts) { if (!set.contains(next)) { set.add(next); queue.add(next); } } } }
圖的深度優先遍歷（dfs）
基本思路
- 利用堆疊實作
- 從源節點開始把節點按照深度放入堆疊，然后彈出
- 每彈出一個節點，把該節點所有沒有進過堆疊的鄰接點放放入堆疊
- 直到堆疊變空
圖解
代碼
//深度優先遍歷一條路走到頭，再往上回傳 public static void dfs(Node node) { if (node == null) { return; } Stack<Node> stack = new Stack<>(); HashSet<Node> set = new HashSet<>(); stack.add(node); set.add(node); System.out.println(node.value); while (!stack.isEmpty()) { Node cur = stack.pop(); for (Node next : cur.nexts) { //如果后代沒有進過堆疊，父壓入堆疊，后代壓入堆疊，列印，break if (!set.contains(next)) { stack.push(cur); stack.push(next); set.add(next); //進堆疊列印 System.out.println(next.value); break; } } } }
圖的拓撲排序演算法
基本思路：
- 在圖中找到所有入度為0的點輸出
- 把所有入度為0的點在圖中刪掉，繼續找入度為0的點輸出，周而復始
- 圖的所有點都被洗掉后，依次輸出的順序就是拓撲排序
要求：有向圖且沒有環
應用：事件安排，編譯順序
圖解：
代碼
public static List<Node> sortedTopology(Graph graph) { // key 某個節點 value 剩余的入度 HashMap<Node, Integer> inMap = new HashMap<>(); // 只有剩余入度為0的點，才進入這個佇列 Queue<Node> zeroInQueue = new LinkedList<>(); //for結束會找出一個入度為0的點 for (Node node : graph.nodes.values()) { //原始圖中每個點的原始入度數 inMap.put(node, node.in); if (node.in == 0) { zeroInQueue.add(node); } } //結果集 List<Node> result = new ArrayList<>(); while (!zeroInQueue.isEmpty()) { Node cur = zeroInQueue.poll(); result.add(cur); for (Node next : cur.nexts) { //cur所有鄰居入度-1 inMap.put(next, inMap.get(next) - 1); if (inMap.get(next) == 0) { zeroInQueue.add(next); } } } return result; }
在學習kruskal與prim之前我們先了解一下什么是最小生成樹，采用百度百科的介紹
一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊，
舉栗子
最小生成樹之krusKal演算法
基本思路：
- 總是從權值最小的變開始考慮，依次考察權值依次變大的邊
- 當前的邊要么進入最小生成樹的集合，要么丟棄
- 如果當前的邊進入最小生成樹的集合中不會形成環，就要當前邊
- 如果當前的邊進入最小生成樹的集合中會形成環，就不要當前邊
- 考察完所有邊之后，最小生成樹的集合也得到了
圖解
代碼：
這里我們用到了前面的并查集，結果回傳我們要的邊的集合，這里做的是無向圖，只是要最后的權值，如果是有向圖的話會少一側
public static class UnionFind { // key 某一個節點， value key節點往上的節點 private HashMap<Node, Node> fatherMap; // key 某一個集合的代表節點, value key所在集合的節點個數 private HashMap<Node, Integer> sizeMap; public UnionFind() { fatherMap = new HashMap<Node, Node>(); sizeMap = new HashMap<Node, Integer>(); } public void makeSets(Collection<Node> nodes) { fatherMap.clear(); sizeMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); sizeMap.put(node, 1); } } private Node findFather(Node n) { Stack<Node> path = new Stack<>(); while(n != fatherMap.get(n)) { path.add(n); n = fatherMap.get(n); } while(!path.isEmpty()) { fatherMap.put(path.pop(), n); } return n; } public boolean isSameSet(Node a, Node b) { return findFather(a) == findFather(b); } public void union(Node a, Node b) { if (a == null || b == null) { return; } Node aDai = findFather(a); Node bDai = findFather(b); if (aDai != bDai) { int aSetSize = sizeMap.get(aDai); int bSetSize = sizeMap.get(bDai); if (aSetSize <= bSetSize) { fatherMap.put(aDai, bDai); sizeMap.put(bDai, aSetSize + bSetSize); sizeMap.remove(aDai); } else { fatherMap.put(bDai, aDai); sizeMap.put(aDai, aSetSize + bSetSize); sizeMap.remove(bDai); } } } } //邊從小到大排序 public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> kruskalMST(Graph graph) { UnionFind unionFind = new UnionFind(); //先將圖中的每個點做成一個集合 unionFind.makeSets(graph.nodes.values()); // 從小的邊到大的邊，依次彈出，小根堆！ PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); for (Edge edge : graph.edges) { // M 條邊 priorityQueue.add(edge); // O(logM) } Set<Edge> result = new HashSet<>(); while (!priorityQueue.isEmpty()) { // M 條邊 Edge edge = priorityQueue.poll(); // O(logM) //如果邊的左右倆測不是同一個集合，要這條邊，合并這倆個節點 if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1) result.add(edge); unionFind.union(edge.from, edge.to); } } return result; } }
最小生成樹之Prim演算法
基本思路：
- 可以從任意節點出發來尋找最小生成樹
- 某個點加入到被選取的點中后，解鎖這個點出發的所有新的邊
- 在所有解鎖的邊中選最小的邊，然后看看這個邊會不會形成環
- 如果會，不要當前邊，繼續考察剩下解鎖的邊中最小的邊（重復3）
- 如果不會，要當前邊，將該邊的指向點加入到被選取的點中（重復2）
- 當所有點都被選取，最小生成樹就得到了
圖解：
代碼
public static class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set<Edge> primMST(Graph graph) { // 解鎖的邊進入小根堆 PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator()); // 哪些點被解鎖出來了 HashSet<Node> nodeSet = new HashSet<>(); // 依次挑選的的邊在result里 Set<Edge> result = new HashSet<>();
//for回圈防止森林 for (Node node : graph.nodes.values()) { // 隨便挑了一個點 // node 是開始點 if (!nodeSet.contains(node)) { nodeSet.add(node); for (Edge edge : node.edges) { // 由一個點，解鎖所有相連的邊 priorityQueue.add(edge); } while (!priorityQueue.isEmpty()) { Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊 Node toNode = edge.to; // 可能的一個新的點 if (!nodeSet.contains(toNode)) { // 不含有的時候，就是新的點 nodeSet.add(toNode); result.add(edge); for (Edge nextEdge : toNode.edges) { priorityQueue.add(nextEdge); } } } } break; } return result; }
總結：
一開始介紹了并查集，主要就是倆個方法issameSet與union，先檢查倆個節點是不是在一個集合中，如果不是的話我們要進行合并集合，小集合的頭掛在大集合的頭上，這里要注意的就是findFather這個方法，里面的重要優化是將整個鏈表
扁平化，這樣我們再來一個新的節點找父節點的時候可以直接找到，不用遍歷，
然后介紹了圖結構，圖結構有很多種，鄰接矩陣，鄰接鏈表等，這里列舉了一種比較萬能的圖結構表達，可以將給定的圖結構轉化成我們熟悉的結構，列舉了一個例子就是[[7,0,4] [4,1,3] [3,2,3] [8,2,4]] ------>[權值，from，to]，
接著介紹了圖的寬度優先遍歷bfs與深度優先遍歷dfs，寬度優先遍歷就是按照層的方式一層一層的往下遍歷，這里需要注意的是與二叉樹的bfs不同的是我們增加了一個set集合，主要是在二叉樹中不存在環的問題，用set可以記錄哪些節點已經
跑過了，不需要再跑，深度優先遍歷就是一條路走到頭，用堆疊記錄著走過的路徑，同樣的set可以保證不重復來回走，
拓撲排序是有前提的，有向圖并且沒有環，主要思路就是在圖中找到所有入度為0的點輸出，然后把所有入度為0的點在圖中刪掉，繼續找入度為0的點輸出，周而復始，直到圖中所有的點被刪掉為止，
最小生成樹介紹了krusKal演算法與Prim演算法，krusKal用到了前面介紹的并查集，思路還是比較簡單的，我們先把所有的邊放入小根堆進行從小到大排序，然后每彈出一個看一下邊左右倆測節點是不是同一個集合，是的話繼續彈出，不是的話合并
這倆個節點，直到小根堆中沒有邊為止，Prim主要思路是先隨便找一個點，然后解鎖它鎖相鄰的邊，在里面選一條最小的邊然后解鎖新的節點，這個新的節點又可以解鎖相鄰的邊，周而復始，直到所有的點都解鎖為止，難懂的地方可能是那個for
回圈，主要是用來防止森林的，平時可能用不到，刪掉也可以，同樣這里我們也利用一個set集合用來記錄哪些點被解鎖了，
另外可能圖解畫的不是很清楚，需要很仔細的看，我會努力提高畫圖的能力，笑，以上代碼均來自左神，不認識的可以去百度，真的是講的非常好的一位老師，這里有寫的不對的地方，歡迎指出，我們共同進步，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296226.html
標籤：其他
上一篇：圖解演算法第一天 -- 二分查找
下一篇：動態規劃