最小生成樹要求：
首先躲履，保證所有點連通见间，其次保證邊的權(quán)重和最低
應用范圍：無向圖
Kruskal（克魯斯卡爾）算法：
思路：
依次找權(quán)值最小的邊，直到遍歷完邊并且不形成環(huán)為止工猜。
實現(xiàn)方法用的并查集缤剧，首先把圖的所有變放到一個小根堆里，然后從小根堆poll域慷，判斷poll出的邊edge的fromNode和toNode在不在并查集里，即他們的父節(jié)點是不是一樣的汗销，如果一樣就說明形成環(huán)了犹褒，如果沒有就把這兩個點加入到并查集合里，執(zhí)行直到小根堆為空
代碼：
public static class UnionFind {
//key 當前結(jié)點 value 父節(jié)點
private HashMap<Node, Node> fatherMap;
//當前集合的大谐谡搿（最后就用頭節(jié)點的大小來表示叠骑，size存在頭節(jié)點中）
private HashMap<Node, Integer> rankMap;
public UnionFind() {
fatherMap = new HashMap<Node, Node>();
rankMap = new HashMap<Node, Integer>();
}
private Node findFather(Node n) {
Node father = fatherMap.get(n);
if (father != n) {
father = findFather(father);
}
fatherMap.put(n, father);
return father;
}
public void makeSets(Collection<Node> nodes) {
fatherMap.clear();
rankMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
rankMap.put(node, 1);
}
}
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 aFather = findFather(a);
Node bFather = findFather(b);
if (aFather != bFather) {
int aFrank = rankMap.get(aFather);
int bFrank = rankMap.get(bFather);
if (aFrank <= bFrank) {
fatherMap.put(aFather, bFather);
rankMap.put(bFather, aFrank + bFrank);
} else {
fatherMap.put(bFather, aFather);
rankMap.put(aFather, aFrank + bFrank);
}
}
}
}
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) {
priorityQueue.add(edge);
}
Set<Edge> result = new HashSet<>();
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
if (!unionFind.isSameSet(edge.from, edge.to)) {
result.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return result;
}
Prim（普里姆）算法：
思路：
創(chuàng)建一個優(yōu)先級隊列（小根堆），創(chuàng)建一個Hashset set用來存已經(jīng)經(jīng)過的節(jié)點削茁，再創(chuàng)建一個Set result 來存結(jié)果邊宙枷，從所有節(jié)點中隨機選一個節(jié)點，判斷該節(jié)點是否在set里茧跋，如果不在就加入慰丛，然后把當前node的所有的邊加入到優(yōu)先級隊列，然后彈出小根堆的堆頂瘾杭，即當前節(jié)點所連邊權(quán)值最小的那一條诅病，然后判斷這條邊所連的節(jié)點toNode，是否在set中如果不在粥烁，就加入贤笆，同時把邊加入到result中，然后再把toNode所連的所有邊加入到優(yōu)先級隊列（小根堆里）讨阻，依次執(zhí)行下去芥永，得出結(jié)果。
總結(jié)起來一句話：隨機找一個節(jié)點钝吮，通過這個節(jié)點找權(quán)值最小的邊埋涧，通過這條邊再找節(jié)點板辽，節(jié)點如果沒遍歷，就繼續(xù)從這個節(jié)點找權(quán)值最小的邊飞袋，最后結(jié)束戳气。
代碼：
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> set = new HashSet<>();
Set<Edge> result = new HashSet<>();
for (Node node : graph.nodes.values()) {
if (!set.contains(node)) {
set.add(node);
for (Edge edge : node.edges) {
priorityQueue.add(edge);
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
Node toNode = edge.to;
if (!set.contains(toNode)) {
set.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
}
return result;
}
注意：代碼上的最開始的超級循環(huán)是用來處理森林的問題，比如一個圖有森林（森林：n棵互不相交的樹）巧鸭，你第一次選的起始點遍歷完后瓶您，就只能處理一棵樹，第二棵沒有處理纲仍，所以這時候遍歷所有節(jié)點結(jié)合判斷set里是否有遍歷的當前node呀袱，即可完成所有樹的最小生成樹的查找。
