Kruskal
什么K演算法，K演算法就是最小生成樹演算法，具體說來，就是對于一張已經存在的圖，如下圖，
**在不破壞連通性的情況下，只留下整體權重最小的邊的集合，就是邊的權值加起來最小，**拿上面圖舉例，把權值100和50的邊去掉就達到了我們的要求（所有可能性中，邊的權值加起來最小的情況）：
演算法流程
先把所有的邊根據權值由小到大排序，假設圖中每個結點都是一個單獨的集合，從權值小的邊開始選，如果有多條權值一樣的邊，無論先選哪條都行，選中某條邊后，看這條邊兩邊的點有沒有在同一個集合里面，沒有在一個集合里，就選上這條邊，并把兩側結點歸在同一個集合里面；如果這條邊兩邊的結點在一個集合里，就不選這條邊，一直到整個圖聯通在一起，
通過上面的分析，很明顯，用并查集來做是最方便的，并查集就是解決兩大片聯通在一起的問題，
如果用戶提供有向圖，那這個演算法肯定沒有問題，如果是無向圖呢？——那就只是邊集合少了一側，整體權重是沒有變化的，
我們再來明確一點，有向圖和無向圖是可以認為沒有明確界限的，無向圖就可以認為是兩邊都有向，所以kruskal演算法無論有向無向都可以，
最后再總結一下K演算法的大概步驟：
注意：不能破環連通性！！！
1)總是從權值最小的邊開始考慮，依次考察權值變大的邊
2)當前的邊要么進入最小生成樹的集合，要么丟棄
3)如果當前的邊進入最小生成樹的集合中不會形成環，就要當前邊,
4)如果當前的邊進入最小生成樹的集合中會形成環，就不要當前邊
5)考察完所有邊之后，最小生成樹的集合也得到了
package com.harrison.class11;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
import com.harrison.class11.Code01_NodeEdgeGraph.*;
public class Code05_Kruskal {
public static class UnionFind{
// key 某一個結點 value：某一個結點往上的結點
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);
}
}
public 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 aHead=findFather(a);
Node bHead=findFather(b);
if(aHead!=bHead) {
int aSetSize=sizeMap.get(aHead);
int bSetSize=sizeMap.get(bHead);
Node big=aSetSize>=bSetSize?aHead:bHead;
Node small=big==aHead?bHead:aHead;
fatherMap.put(small, big);
sizeMap.put(big, aSetSize+bSetSize);
sizeMap.remove(small);
}
}
}
public static class EdgeComparator implements Comparator<Edge>{
public int compare(Edge e1,Edge e2) {
return e1.weight=e2.weight;
}
}
public static Set<Edge> kruskalMST(Graph graph){
UnionFind unionFind=new UnionFind();
unionFind.makeSets(graph.nodes.values());
PriorityQueue<Edge> pq=new PriorityQueue<>();
for(Edge edge:graph.edges) {
pq.add(edge);
}
Set<Edge> ans=new HashSet<>();
while(!pq.isEmpty()) {
Edge edge=pq.poll();
if(!unionFind.isSameSet(edge.from, edge.to)) {
ans.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/390385.html
標籤：其他
上一篇：新專案如何技術選型以及落地實作
下一篇：最小生成樹演算法——Prim