一：無向帶權(quán)圖的最小生成樹
無向帶權(quán)圖是圖論算法領(lǐng)域中的一種基礎(chǔ)模型。它的代碼實現(xiàn)我們就不在這篇文章中介紹了，大家可以參考文章后面給出的代碼鏈接。下圖為一個無向帶權(quán)圖的示例：
接下來我們著重介紹一下圖的生成樹與最小生成樹的概念。
什么是圖的生成樹呢？
首先，只有一個聯(lián)通圖才有會有圖的生成樹，也就是說，給定的圖的聯(lián)通分量的個數(shù)必須是 1 。
然后，在一個聯(lián)通圖 中，如果取它全部頂點和一部分邊構(gòu)成一個子圖
，若子圖
的所有邊能夠使得全部的頂點聯(lián)通且不形成任何的回路，則稱子圖
為原圖
的一棵生成樹。
上面的兩個圖都是示例給定圖的生成樹。我們看到，一個圖可能存在多個生成樹，生成樹不同，每棵樹的權(quán)（即：樹中所有邊上的權(quán)值總和）也可能不同。譬如左邊的生成樹的權(quán)為 19，右邊的生成樹的權(quán)為 14。
所謂的最小生成樹（Minimum Spanning Tree）指的就是，帶權(quán)圖的生成樹中，權(quán)最小的生成樹。
右邊的生成樹（用藍(lán)色節(jié)點標(biāo)注）實際上就是我們給定的示例圖的最小生成樹。
我們?yōu)槭裁匆蠼庾钚∩蓸?？求解帶?quán)圖的最小生成樹有什么意義呢？
舉個例子：假設(shè)上圖表示 n 個城市之間的通信網(wǎng)線路（其中頂點表示城市，邊表示兩個城市之間的通信線路，邊上的權(quán)值表示線路的具體造價）。
我們可以通過求該圖的最小生成樹達到求解通信線路造價費用最小的方案。求解最小生成樹的意義還有很多，大家可以自行了解一下。
二：Kruskal 算法
Kruskal 算法是求解無向帶權(quán)圖的最小生成樹的經(jīng)典算法之一。
Kruskal 算法的思想是每次都選擇圖中的一個權(quán)值最小的邊添加到結(jié)果集中，期間要保證結(jié)果集不會產(chǎn)生環(huán)，當(dāng)結(jié)果集滿足生成樹的條件時，那么其必然是一棵最小生成樹。
我們使用該示例圖作為演示，看一下 Kruskal 算法的具體執(zhí)行流程：
上圖為 Kruskal 算法的執(zhí)行流程。我們每次都選擇權(quán)值最小的邊來構(gòu)建圖的生成樹。在第四步，由于三條權(quán)值為 4 的邊都會使得生成樹產(chǎn)生環(huán)，即這三條邊不符合生成樹的定義，所以并沒有添加到結(jié)果集當(dāng)中。
不難發(fā)現(xiàn)，Kruskal 算法的本質(zhì)就是貪心策略。接下來，我們就去證明一下 Kruskal 算法為什么可以得到無向帶權(quán)圖的最小生成樹？這個貪心策略為什么是正確的？
Kruskal 算法的正確性證明與切分定理
在了解什么是 切分定理（Cut Property） 之前，首先，我們要了解兩個概念：切分（Cut） 與 橫切邊（Crossing Edge）。
切分與橫切邊是指：將圖中的頂點分為兩部分，就稱這是圖的一個切分。如果一個邊的兩個端點，屬于切分不同的兩邊，則這個邊稱為橫切邊。
譬如上圖中，我們將圖中所有的頂點分成紅色和藍(lán)色兩部分，這就是該圖的一個切分。1-4、1-3、0-3 和 2-4 這四條邊的兩個端點屬于切分不同的兩邊，所以，這四條邊就是該切分的橫切邊。
拓展一下，在圖論領(lǐng)域中，還有一個非常重要的概念叫二分圖（Bipartite）。
二分圖具有以下特性：
- 圖中所有的頂點可以分成不相交的兩個部分
- 所有的邊的兩個端點都隸屬于不同的部分
如上圖所示，該圖就是一個二分圖。
在引入了切分這個概念之后，我們可以重新定義二分圖的概念，二分圖就是能在圖中找到一個切分，使得圖中的所有邊都是橫切邊的圖。
好，那么話說回來，什么是切分定理呢？
切分定理就是，任意一個切分的橫切邊中權(quán)值最小的那條邊，一定是最小生成樹的一條邊。
該圖的切分中，1-4、1-3、0-3 和 2-4 這四條邊為橫切邊，它們的權(quán)值分別為 3、4、7 和 4，這里面，1-4 這條邊的權(quán)值最小，所以，根據(jù)切分定理，1-4 這條邊一定是該圖的最小生成樹中的一條邊。
譬如，該圖的這個切分中，1-4、1-3、0-3 和 2-4 這四條邊為橫切邊，它們的權(quán)值分別為 3、4、7 和 4，這里面，1-4 這條邊的權(quán)值最小，所以，根據(jù)切分定理，1-4 這條邊一定是該圖的最小生成樹中的一條邊。
切分定理該如何證明呢？
我們知道，最小生成樹的所有頂點一定是聯(lián)通的，所以，該切分的最小生成樹對應(yīng)的左邊的四個頂點之間是聯(lián)通的，右邊的三個頂點也是聯(lián)通的，左邊和右邊之間必然存在一條邊使得左右兩邊可以聯(lián)通。我們就不難想出，使得左右兩邊之間聯(lián)通形成最小生成樹的那條邊，必然是橫切邊中權(quán)值最小的那條邊。
所以，通過切分定理我們就知道了，Kruskal 算法每次都選擇一個最短（權(quán)值最?。┑倪?，在這條邊沒有使得當(dāng)前的生成樹形成環(huán)的前提下，我們每一次相當(dāng)于是對該圖一個切分，選擇了最短的橫切邊，那么這條邊就一定在最小生成樹中！
Kruskal 算法的實現(xiàn)
在講解如何實現(xiàn) Kruskal 算法前，我們需要了解一種數(shù)據(jù)結(jié)構(gòu)：并查集。并查集在 Kruskal 算法中有著非常重要的作用，它用來判斷當(dāng)前的邊是否讓生成樹形成了環(huán)。
并查集
并查集（UnionFind）是一種樹型的數(shù)據(jù)結(jié)構(gòu)。
并查集的主要功能有兩個：
- 判斷元素 A 所在的集合是否和元素 B 所在的集合是同一個集合
- 將元素 A 所在的集合與元素 B 所在的集合合并
并查集的初始化
并查集的初始化是將樣本量為 N 的數(shù)據(jù)中每個元素構(gòu)成一個單元素的集合。
每一個元素作為一個節(jié)點，同時自己指向自己，成為 標(biāo)記節(jié)點 ,作為一個單元素構(gòu)成的集合。
我們維護兩個哈希表:
Map<Integer,Integer> map;
Map<Integer,Integer> size;
第一個 Map 的 Key 存儲當(dāng)前節(jié)點的值，Value 存儲該節(jié)點指向的父節(jié)點的值；第二個 Map 的 Key 存儲當(dāng)前節(jié)點的值，Value 存儲該節(jié)點所在的集合共有多少元素。
并查集的初始化代碼
public Map<Integer,Integer> map;
public Map<Integer,Integer> size;
public UnionFind(int n){
map = new HashMap<>();
size = new HashMap<>();
for(int i = 0; i < n; i++){
// 最開始每個元素自己指向自己，自己成為根節(jié)點作為一個單元素構(gòu)成的集合
map.put(i,i);
// 每個集合只有一個元素
size.put(i,1);
}
}
判斷 A 和 B 所在的集合是否為同一個集合
判斷元素 A 和 B 所在的集合是否為同一個集合的方法很簡單，我們只需要找到 A 所在的集合的根節(jié)點，找到 B 所在的集合的根節(jié)點，然后判斷這兩個元素的根節(jié)點是否為同一個節(jié)點即可。如果二者的根結(jié)點相同，就說明，A 和 B 在同一個集合當(dāng)中。
我們初始化的 map 存儲的 key 為這個節(jié)點自身，map 存儲的 value 為該節(jié)點的父節(jié)點。所以，我們很容易就可以寫出尋找一個節(jié)點的根節(jié)點的代碼：
public Node find(Node node){
Node root = map.get(node);
if(root != node){ // 因為根節(jié)點是自己指向自己的，所以找到根節(jié)點以后遞歸就會終止
root = find(root);
}
return root;
}
不過，這個代碼存在效率的問題，譬如：
假設(shè)有并查集如上圖所示，我們需要查尋 4 和 2 的根節(jié)點。
元素 2 只需要走一步就可以找到根節(jié)點，而元素 4 需要走兩步才能找到根節(jié)點。
隨著并查集的數(shù)據(jù)量越來越大，有可能就會導(dǎo)致樹的高度越來越高，查詢速率越來越慢。為了提升下次查詢的效率，我們需要做樹的扁平化處理。我們在查詢后知道，節(jié)點 4 的根節(jié)點為 1 ；所以，我們在查詢到 4 的根節(jié)點之后，直接讓 4 指向根節(jié)點 1，然后再返回根節(jié)點，這種處理就是扁平化處理。
當(dāng)然，該操作也并不難，只需要添加一句代碼即可：
public Node find(Node node){
Node root = map.get(node);
if(root != node){ // 因為根節(jié)點是自己指向自己的，所以找到根節(jié)點以后遞歸就會終止
root = find(root);
}
map.put(node,root); // 扁平化處理
return root;
}
在解決了查詢元素的根結(jié)點的邏輯后，查詢 A 和 B 所在的集合是否為同一集合的代碼就非常簡單了：
public boolean isSameSet(int p, int q) {
return find(p) == find(q);
}
合并 A 和 B 所在的集合
并查集的另一個重要的功能就是合并 A 和 B 元素所在的集合。
已知：節(jié)點a所在集合的根節(jié)點aRoot ，節(jié)點b所在的集合的根節(jié)點bRoot；以及，節(jié)點a所在的集合的元素數(shù)量為aSize，節(jié)點b所在的集合的元素數(shù)量為bSize。
如果，aSize < bSize，那么我們就讓節(jié)點a所在的集合向節(jié)點b所在的集合合并。
如果，bSize < aSize，那么我們就讓節(jié)點b所在的集合向節(jié)點a所在的集合合并。
其代碼如下：
public void union(int p,int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot != qRoot){
int pSize = size.get(pRoot);
int qSize = size.get(qRoot);
if(pSize < qSize){
map.put(pRoot,qRoot);
size.put(qRoot,pSize + qSize);
}else {
map.put(qRoot,pRoot);
size.put(pRoot,qSize + pSize);
}
}
}
Kruskal 算法
Kruskal 算法的邏輯流程如下：
- 判斷圖是否是一個聯(lián)通圖，即判斷該圖的聯(lián)通分量是否為 1，如果該圖不是一個聯(lián)通圖，就沒有最小生成樹
- 遍歷圖中所有的邊，將所有的邊添加到一個集合 edges 中，按照邊權(quán)值的大小進行排序
- 初始化并查集，N 為圖的頂點的個數(shù)
- 遍歷集合 edges，對每一條邊 edge 的兩個頂點進行判斷：
- 如果這兩個頂點不在一個集合中，說明這兩個頂點所在的集合不聯(lián)通，我們就將這條邊添加到最小生成樹的結(jié)果集中，并合并這兩個頂點所在的集合；
- 如果這兩個頂點在一個集合中，就說明如果向當(dāng)前的生成樹中添加了這條邊后將會產(chǎn)生環(huán)，即：不滿足生成樹的定義
Kruskal 算法的 Java 代碼
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Kruskal {
private WeightedGraph G;
private List<WeightedEdge> minimumSpanningTree;
public Kruskal(WeightedGraph G) {
this.G = G;
minimumSpanningTree = new ArrayList<>();
// 判斷圖的聯(lián)通分量是否為 1；如果大于 1 則直接返回，說明該圖沒有最小生成樹
CC cc = new CC(G);
if (cc.count() > 1) return;
// Kruskal
List<WeightedEdge> edges = new ArrayList<>();
for (int v = 0; v < G.V(); v++)
for (int w : G.adj(v))
if (v < w)
edges.add(new WeightedEdge(v, w, G.getWeight(v, w)));
Collections.sort(edges);
UnionFind unionFind = new UnionFind(G.V());
for (WeightedEdge edge : edges) {
int v = edge.getV();
int w = edge.getW();
if (!unionFind.isSameSet(v, w)) {
minimumSpanningTree.add(edge);
unionFind.union(v, w);
}
}
}
/**
* 返回最小生成樹的結(jié)果集
*
* @return
*/
public List<WeightedEdge> result() {
return minimumSpanningTree;
}
}
上圖中，右圖為左圖的最小生成樹，我們對左邊的圖進行測試：
測試程序返回的輸出結(jié)果為：
[(1-2：1), (3-4：1), (0-1：2), (0-5：2), (1-4：3), (3-6：5)]
可以看到，我們的 Kruskal 算法執(zhí)行結(jié)果是正確的。
三：Prim 算法
除了 Kruskal 算法外，Prim 算法也是解決最小生成樹問題的一種常用算法。相比于 Kruskal 算法，Prim 算法可以說更巧妙地運用了切分定理。
Prim 算法的執(zhí)行流程是這樣的：
從第一個頂點開始，該頂點與圖中其他頂點就構(gòu)成了一個切分，我們找到當(dāng)前切分最短的橫切邊。然后不斷擴展切分，直到?jīng)]有切分時，就找到了圖的最小生成樹。詳細(xì)的過程可以參考下面的 PPT：
<
優(yōu)先隊列
在實現(xiàn) Prim 算法之前，我們也需要了解一種數(shù)據(jù)結(jié)構(gòu)，那就是優(yōu)先隊列（PriorityQueue）。
優(yōu)先隊列是是一種特殊的隊列。在優(yōu)先隊列中每個元素都有各自的優(yōu)先級，優(yōu)先級最高的元素最先得到服務(wù)；優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務(wù)。而優(yōu)先隊列往往使用堆來實現(xiàn)。
對于優(yōu)先隊列這樣一種數(shù)據(jù)結(jié)構(gòu)，我們并不需要像并查集一樣去自己手動實現(xiàn)。幾乎所有語言的標(biāo)準(zhǔn)庫中，都有優(yōu)先隊列這樣一種數(shù)據(jù)結(jié)構(gòu)。
在 Java 中，PriorityQueue 默認(rèn)的底層實現(xiàn)是最小堆。
我們來看一個示例程序：
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueTest {
@Test
void test(){
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(2);
pq.offer(1);
while(!pq.isEmpty())
System.out.println(pq.poll());
}
}
該程序的輸出結(jié)果為：
1
2
3
Prim 算法的實現(xiàn)
Prim 算法邏輯流程如下：
- 判斷圖是否是一個聯(lián)通圖，即判斷該圖的聯(lián)通分量是否為 1，如果該圖不是一個聯(lián)通圖，就不存在最小生成樹
- 初始化一個布爾型數(shù)組 visited，長度為圖中頂點的個數(shù)。對應(yīng)上面的 PPT ，true 表示節(jié)點的顏色為藍(lán)色，false 表示節(jié)點的顏色為黑色
- 初始化優(yōu)先隊列，隊列中存放的是當(dāng)前切分所有的橫切邊，在不斷擴展切分，直到?jīng)]有切分時，此時的優(yōu)先隊列為空，也就找到了最小生成樹
- 將第一個頂點渲染為藍(lán)色(
visited[0] = true)，與這個頂點相連的所有的邊都是橫切邊，我們將所有的邊都加入到優(yōu)先隊列中 - 將優(yōu)先隊列的首個元素出隊
- 如果出隊的邊的兩個頂點均為藍(lán)色，則跳過
- 否則，就將該邊添加到最小生成樹的結(jié)果集中
- 將新添加的邊的另一個頂點 p 渲染為藍(lán)色
- 找到頂點 p 所有的相鄰頂點，如果相鄰頂點 w 不是藍(lán)色，就將 p-w 這條邊添加到優(yōu)先隊列中
- 循環(huán)上述操作，直至優(yōu)先隊列為空，也就找到了最小生成樹
Prim 算法的 Java 代碼
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class Prim {
private WeightedGraph G;
private List<WeightedEdge> minimumSpanningTree;
public Prim(WeightedGraph G) {
this.G = G;
minimumSpanningTree = new ArrayList<>();
// 判斷該圖的聯(lián)通分量是否為 1，如果大于 1 說明不存在最小生成樹
CC cc = new CC(G);
if (cc.count() > 1) return;
// Prim
// true 表示為藍(lán)色的頂點 false 表示為黑色的頂點
boolean[] visited = new boolean[G.V()];
visited[0] = true;
Queue<WeightedEdge> pq = new PriorityQueue<>(); // 最小堆
for (int w : G.adj(0))
pq.offer(new WeightedEdge(0, w, G.getWeight(0, w)));
while (!pq.isEmpty()) {
WeightedEdge minEdge = pq.remove();
if (visited[minEdge.getV()] && visited[minEdge.getW()])
continue;
minimumSpanningTree.add(minEdge);
int p = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV();
visited[p] = true;
for (int w : G.adj(p))
if (!visited[w])
pq.offer(new WeightedEdge(w, p, G.getWeight(w, p)));
}
}
/**
* 返回最小生成樹的結(jié)果集
*
* @return
*/
public List<WeightedEdge> result() {
return minimumSpanningTree;
}
}
我們依舊使用左圖進行測試，右圖為左圖的最小生成樹。
測試程序返回的輸出結(jié)果為：
[(0-1：2), (2-1：1), (0-5：2), (4-1：3), (3-4：1), (6-3：5)]
可以看到，我們的 Prim 算法的驗證結(jié)果是正確的。
四：總結(jié)
本文介紹了 Kruskal 算法與 Prim 算法，介紹了無向有權(quán)圖的最小生成樹以及求解最小生成樹的意義。Kruskal 算法與 Prim 算法的核心思想實際上就是切分定理，只不過這兩種算法在使用切分定理時，采用了不同的策略。Kruskal 算法是貪心策略，每次都選取圖中權(quán)值最小的那條邊來構(gòu)建生成樹；Prim 算法則是從一個頂點出發(fā)，不斷擴展圖的切分，直到?jīng)]有切分為止，就構(gòu)建出了最小生成樹。
本文的使用的代碼鏈接：
- 代碼：https://github.com/jinrunheng/datastructure-and-algorithm/tree/main/src/main/java/com/github/datastructureandalgorithm/graph/chapter11
- 測試：https://github.com/jinrunheng/datastructure-and-algorithm/tree/main/src/test/java/com/github/datastructureandalgorithm/graph/chapter11
好啦，至此為止，這一篇文章我就介紹完畢了～歡迎大家關(guān)注我的公眾號【kim_talk】，在這里希望你可以收獲更多的知識，我們下一期再見！
