Kruskal算法
以Prim算法一樣，Kruskal算法也可以用來計(jì)算圖的最小生成樹。
Kruskal算法執(zhí)行過程
首先了解以下Kruskal算法的描述
按照邊的權(quán)重順序（從小到大）將邊加入到生成樹中，直到生成樹中含有V - 1 條邊位置（V是頂點(diǎn)數(shù)量）
- 如果待加入的這條邊加入后，會(huì)導(dǎo)致樹成環(huán)，則不加入這條邊（從經(jīng)驗(yàn)來講，從第3條邊開始，就可能會(huì)與生成樹形成環(huán)）
結(jié)合圖片，再來走一遍Kruskal的執(zhí)行流程，假設(shè)現(xiàn)在有圖如下
根據(jù)Kruskal算法的邏輯，首先會(huì)選擇權(quán)值最小的一條邊。所以HG這條邊一定會(huì)成為最小生成樹的一條邊
選出一條邊以后，再?gòu)氖Ｏ碌倪呏羞x擇一條權(quán)值最小的邊?，F(xiàn)在剩下的邊中，最小權(quán)值是2，并且有兩條，這種情況，選擇任意一條都可以，假設(shè)現(xiàn)在選擇的是IC這一條邊作為生成樹的一條邊，最終的結(jié)果如下
然后再繼續(xù)從生下的邊中，選擇一條邊作為生成樹的一條邊。但是由于現(xiàn)在已經(jīng)找出了2條邊作為生成樹的邊，所以現(xiàn)在找出第三條以后，就需要判斷新找到的邊，是否會(huì)導(dǎo)致原來的生成樹成環(huán)，如果不會(huì)，就將這條邊作為生成樹的邊，如果會(huì)，則繼續(xù)找權(quán)值次小的一條邊，直到找到不成環(huán)的邊位置。所以在找第三條邊時(shí)，依然會(huì)找出權(quán)值為2的邊GF，最為生成樹的邊。最終的結(jié)果如下
繼續(xù)依照上面的邏輯，尋找權(quán)值最小的邊，所以從剩下的邊中，找到了權(quán)值為4的邊，本次先選擇AB這條邊作為生成樹的一條邊，所以選擇后的結(jié)果如下
繼續(xù)從權(quán)值最小的邊中尋找合適的邊作為生成樹的邊，本次選擇到的依然是權(quán)值為4的邊CF，所以選擇后的結(jié)果如下
繼續(xù)中權(quán)值最小的邊中尋找合適的邊作為生成樹的邊，本次最小權(quán)值為6，是IG邊，不過請(qǐng)注意，這次不能選擇這條邊作為生成樹的邊，因?yàn)橐坏┻x擇這條邊，就會(huì)導(dǎo)致原生成樹成環(huán)，所以不能選擇這條邊。
那就一次從小到大進(jìn)行尋找，找到權(quán)值為7的邊，不過請(qǐng)注意，權(quán)值為7的邊IH一旦選擇的話，也會(huì)導(dǎo)致生成樹成環(huán)，所以依然不能選，所以最終選擇的邊是CD，所以選擇后的結(jié)果如下
然后再?gòu)氖Ｏ碌倪呏袑ふ乙粭l邊，由于前面已經(jīng)排除了兩條邊，所以本次從8開始選擇，由于現(xiàn)在有兩條邊的權(quán)值都為8，所以選擇任意一條均可，在本示例中以選擇AH邊為例，最終選擇后的結(jié)果如下
繼續(xù)從剩下的邊中，尋找權(quán)值最小的邊，由于本次權(quán)值最小的邊BC會(huì)導(dǎo)致生成樹成環(huán)，所以不能選，所以最終選擇的是權(quán)值為9的邊DE，所以選擇后的結(jié)果如下
現(xiàn)在還剩權(quán)值為10,11,14的邊沒有選，但是到現(xiàn)在，算法就已經(jīng)結(jié)束了。因?yàn)楝F(xiàn)在選擇的邊的數(shù)量，已經(jīng)達(dá)到了V - 1
所以，通過Kruskal算法，最終計(jì)算出來的最小生成樹如下所示
解決判斷是否成環(huán)的問題
那應(yīng)該如何判斷新加入的邊是否會(huì)導(dǎo)致生成樹成環(huán)呢？
可以利用并查集來判斷即將加入的點(diǎn)是否成員的問題。判斷的邏輯如下
- 將選擇的邊中的兩個(gè)點(diǎn)利用并查集合并到一個(gè)集合中
- 由于并查集的特性，如果合并的邊，其中有一個(gè)頂點(diǎn)已經(jīng)在并查集的集合中，新加入的邊與原來的邊會(huì)合并到一個(gè)集合中，例如先加入的邊HG與即將加入的邊GF，最終會(huì)合并到一個(gè)集合中。否則就會(huì)保存到不同的集合中
- 如果新選中的邊，兩個(gè)頂點(diǎn)都在并查集的同一個(gè)集合中，那么就會(huì)導(dǎo)致生成樹成環(huán)，例如集合中的頂點(diǎn)H,G,F,CI，如果現(xiàn)在將邊IG加入，就會(huì)成環(huán)。所以I,G兩個(gè)頂點(diǎn)現(xiàn)在是在同一個(gè)集合中，所以利用并查集的話，可以很容易的判斷出新加入的邊是否會(huì)導(dǎo)致生成樹成環(huán)。
結(jié)合前面的分析，最終Kruskal算法的實(shí)現(xiàn)如下
private Set<EdgeInfo<V, E>> kruskal() {
int edgeSize = vertices.size() - 1;
if (edgeSize == -1) return null;
MinHeap<Edge<V,E>> heap = new MinHeap<>(edges,edgeComparator);
Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
UnionFind<Vertex<V,E>> uf = new UnionFind<>();
vertices.forEach((V v , Vertex<V,E> vertex) ->{
uf.makeSet(vertex);
});
while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
Edge<V,E> edge = heap.remove();
if (uf.isSame(edge.from,edge.to)) continue;
edgeInfos.add(edge.info());
uf.union(edge.from,edge.to);
}
return edgeInfos;
}
完！
