一文詳細(xì)了解Prim最小生成樹算法

讀完本文，可以去力扣解決如下題目：

本文是第 7 篇圖論算法文章，先列舉一下我之前寫過的圖論算法：

1、圖論算法基礎(chǔ)

2、二分圖判定算法

3、環(huán)檢測和拓?fù)渑判蛩惴?/span>

4、Dijkstra 最短路徑算法

5、Union Find 并查集算法

6、Kruskal 最小生成樹算法

像圖論算法這種高級算法雖然不算難，但是閱讀量普遍比較低，我本來是不想寫 Prim 算法的，但考慮到算法知識結(jié)構(gòu)的完整性，我還是想把 Prim 算法的坑填上，這樣所有經(jīng)典的圖論算法就基本完善了。

Prim 算法和 Kruskal 算法都是經(jīng)典的最小生成樹算法，閱讀本文之前，希望你讀過前文Kruskal 最小生成樹算法，了解最小生成樹的基本定義以及 Kruskal 算法的基本原理，這樣就能很容易理解 Prim 算法邏輯了。

對比 Kruskal 算法

圖論的最小生成樹問題，就是讓你從圖中找若干邊形成一個邊的集合mst，這些邊有以下特性：

1、這些邊組成的是一棵樹（樹和圖的區(qū)別在于不能包含環(huán)）。

2、這些邊形成的樹要包含所有節(jié)點。

3、這些邊的權(quán)重之和要盡可能小。

那么 Kruskal 算法是使用什么邏輯滿足上述條件，計算最小生成樹的呢？

首先，Kruskal 算法用到了貪心思想，來滿足權(quán)重之和盡可能小的問題：

先對所有邊按照權(quán)重從小到大排序，從權(quán)重最小的邊開始，選擇合適的邊加入mst集合，這樣挑出來的邊組成的樹就是權(quán)重和最小的。

其次，Kruskal 算法用到了Union-Find 并查集算法，來保證挑選出來的這些邊組成的一定是一棵「樹」，而不會包含環(huán)或者形成一片「森林」：

如果一條邊的兩個節(jié)點已經(jīng)是連通的，則這條邊會使樹中出現(xiàn)環(huán)；如果最后的連通分量總數(shù)大于 1，則說明形成的是「森林」而不是一棵「樹」。

那么，本文的主角 Prim 算法是使用什么邏輯來計算最小生成樹的呢？

首先，Prim 算法也使用貪心思想來讓生成樹的權(quán)重盡可能小，也就是「切分定理」，這個后文會詳細(xì)解釋。

其次，Prim 算法使用BFS 算法思想和visited布爾數(shù)組避免成環(huán)，來保證選出來的邊最終形成的一定是一棵樹。

Prim 算法不需要事先對所有邊排序，而是利用優(yōu)先級隊列動態(tài)實現(xiàn)排序的效果，所以我覺得 Prim 算法類似于 Kruskal 的動態(tài)過程。

下面介紹一下 Prim 算法的核心原理：切分定理

切分定理

「切分」這個術(shù)語其實很好理解，就是將一幅圖分為兩個不重疊且非空的節(jié)點集合：

紅色的這一刀把圖中的節(jié)點分成了兩個集合，就是一種「切分」，其中被紅線切中的的邊（標(biāo)記為藍色）叫做「橫切邊」。

PS：記住這兩個專業(yè)術(shù)語的意思，后面我們會頻繁使用這兩個詞，別搞混了。

當(dāng)然，一幅圖肯定可以有若干種切分，因為根據(jù)切分的定義，只要你能一刀把節(jié)點分成兩部分就行。

接下來我們引入「切分定理」：

對于任意一種「切分」，其中權(quán)重最小的那條「橫切邊」一定是構(gòu)成最小生成樹的一條邊。

這應(yīng)該很容易證明，如果一幅加權(quán)無向圖存在最小生成樹，假設(shè)下圖中用綠色標(biāo)出來的邊就是最小生成樹：

那么，你肯定可以找到若干「切分」方式，將這棵最小生成樹切成兩棵子樹。比如下面這種切分：

你會發(fā)現(xiàn)，任選一條藍色的「橫切邊」都可以將這兩棵子樹連接起來，構(gòu)成一棵生成樹。

那么為了讓最終這棵生成樹的權(quán)重和最小，你說你要怎么選？

肯定選權(quán)重最小的那條「橫切邊」對吧，這就證明了切分定理。

關(guān)于切分定理，你也可以用反證法證明：

給定一幅圖的最小生成樹，那么隨便給一種「切分」，一定至少有一條「橫切邊」屬于最小生成樹。

假設(shè)這條「橫切邊」不是權(quán)重最小的，那說明最小生成樹的權(quán)重和就還有再減小的余地，那這就矛盾了，最小生成樹的權(quán)重和本來就是最小的，怎么再減？所以切分定理是正確的。

有了這個切分定理，你大概就有了一個計算最小生成樹的算法思路了：

既然每一次「切分」一定可以找到最小生成樹中的一條邊，那我就隨便切唄，每次都把權(quán)重最小的「橫切邊」拿出來加入最小生成樹，直到把構(gòu)成最小生成樹的所有邊都切出來為止。

嗯，可以說這就是 Prim 算法的核心思路，不過具體實現(xiàn)起來，還是要有些技巧的。

因為你沒辦法讓計算機理解什么叫「隨便切」，所以應(yīng)該設(shè)計機械化的規(guī)則和章法來調(diào)教你的算法，并盡量減少無用功。

Prim 算法實現(xiàn)

我們思考算法問題時，如果問題的一般情況不好解決，可以從比較簡單的特殊情況入手，Prim 算法就是使用的這種思路。

按照「切分」的定義，只要把圖中的節(jié)點切成兩個不重疊且非空的節(jié)點集合即可算作一個合法的「切分」，那么我只切出來一個節(jié)點，是不是也算是一個合法的「切分」？

是的，這是最簡單的「切分」，而且「橫切邊」也很好確定，就是這個節(jié)點的邊。

那我們就隨便選一個點，假設(shè)就從A點開始切分：

既然這是一個合法的「切分」，那么按照切分定理，這些「橫切邊」AB, AF中權(quán)重最小的邊一定是最小生成樹中的一條邊：

好，現(xiàn)在已經(jīng)找到最小生成樹的第一條邊（邊AB），然后呢，如何安排下一次「切分」？

按照 Prim 算法的邏輯，我們接下來可以圍繞A和B這兩個節(jié)點做切分：

然后又可以從這個切分產(chǎn)生的橫切邊（圖中藍色的邊）中找出權(quán)重最小的一條邊，也就又找到了最小生成樹中的第二條邊BC：

接下來呢？也是類似的，再圍繞著A, B, C這三個點做切分，產(chǎn)生的橫切邊中權(quán)重最小的邊是BD，那么BD就是最小生成樹的第三條邊：

接下來再圍繞A, B, C, D這四個點做切分……

Prim 算法的邏輯就是這樣，每次切分都能找到最小生成樹的一條邊，然后又可以進行新一輪切分，直到找到最小生成樹的所有邊為止。

這樣設(shè)計算法有一個好處，就是比較容易確定每次新的「切分」所產(chǎn)生的「橫切邊」。

比如回顧剛才的圖，當(dāng)我知道了節(jié)點A, B的所有「橫切邊」（不妨表示為cut({A, B})），也就是圖中藍色的邊：

是否可以快速算出cut({A, B, C})，也就是節(jié)點A, B, C的所有「橫切邊」有哪些？

是可以的，因為我們發(fā)現(xiàn)：

cut({A,B,C})=cut({A,B})+cut({C})

而cut({C})就是節(jié)點C的所有鄰邊：

這個特點使我們用我們寫代碼實現(xiàn)「切分」和處理「橫切邊」成為可能：

在進行切分的過程中，我們只要不斷把新節(jié)點的鄰邊加入橫切邊集合，就可以得到新的切分的所有橫切邊。

當(dāng)然，細(xì)心的讀者肯定發(fā)現(xiàn)了，cut({A, B})的橫切邊和cut({C})的橫切邊中BC邊重復(fù)了。

不過這很好處理，用一個布爾數(shù)組inMST輔助，防止重復(fù)計算橫切邊就行了。

最后一個問題，我們求橫切邊的目的是找權(quán)重最小的橫切邊，怎么做到呢？

很簡單，用一個優(yōu)先級隊列存儲這些橫切邊，就可以動態(tài)計算權(quán)重最小的橫切邊了。

明白了上述算法原理，下面來看一下 Prim 算法的代碼實現(xiàn)：

classPrim{
//核心數(shù)據(jù)結(jié)構(gòu)，存儲「橫切邊」的優(yōu)先級隊列
privatePriorityQueue<int[]>pq;
//類似visited數(shù)組的作用，記錄哪些節(jié)點已經(jīng)成為最小生成樹的一部分
privateboolean[]inMST;
//記錄最小生成樹的權(quán)重和
privateintweightSum=0;
//graph是用鄰接表表示的一幅圖，
//graph[s]記錄節(jié)點s所有相鄰的邊，
//三元組int[]{from,to,weight}表示一條邊
privateList<int[]>[]graph;

publicPrim(List<int[]>[]graph){
this.graph=graph;
this.pq=newPriorityQueue<>((a,b)->{
//按照邊的權(quán)重從小到大排序
returna[2]-b[2];
});
//圖中有n個節(jié)點
intn=graph.length;
this.inMST=newboolean[n];

//隨便從一個點開始切分都可以，我們不妨從節(jié)點0開始
inMST[0]=true;
cut(0);
//不斷進行切分，向最小生成樹中添加邊
while(!pq.isEmpty()){
int[]edge=pq.poll();
intto=edge[1];
intweight=edge[2];
if(inMST[to]){
//節(jié)點to已經(jīng)在最小生成樹中，跳過
//否則這條邊會產(chǎn)生環(huán)
continue;
}
//將邊edge加入最小生成樹
weightSum+=weight;
inMST[to]=true;
//節(jié)點to加入后，進行新一輪切分，會產(chǎn)生更多橫切邊
cut(to);
}
}

//將s的橫切邊加入優(yōu)先隊列
privatevoidcut(ints){
//遍歷s的鄰邊
for(int[]edge:graph[s]){
intto=edge[1];
if(inMST[to]){
//相鄰接點to已經(jīng)在最小生成樹中，跳過
//否則這條邊會產(chǎn)生環(huán)
continue;
}
//加入橫切邊隊列
pq.offer(edge);
}
}

//最小生成樹的權(quán)重和
publicintweightSum(){
returnweightSum;
}

//判斷最小生成樹是否包含圖中的所有節(jié)點
publicbooleanallConnected(){
for(inti=0;iif(!inMST[i]){
returnfalse;
}
}
returntrue;
}
}

明白了切分定理，加上詳細(xì)的代碼注釋，你應(yīng)該能夠看懂 Prim 算法的代碼了。

這里我們可以再回顧一下本文開頭說的 Prim 算法和Kruskal 算法的聯(lián)系：

Kruskal 算法是在一開始的時候就把所有的邊排序，然后從權(quán)重最小的邊開始挑選屬于最小生成樹的邊，組建最小生成樹。

Prim 算法是從一個起點的切分（一組橫切邊）開始執(zhí)行類似 BFS 算法的邏輯，借助切分定理和優(yōu)先級隊列動態(tài)排序的特性，從這個起點「生長」出一棵最小生成樹。

說到這里，Prim 算法的時間復(fù)雜度是多少呢？

這個不難分析，復(fù)雜度主要在優(yōu)先級隊列pq的操作上，由于pq里面裝的是圖中的「邊」，假設(shè)一幅圖邊的條數(shù)為E，那么最多操作O(E)次pq。每次操作優(yōu)先級隊列的時間復(fù)雜度取決于隊列中的元素個數(shù)，取最壞情況就是O(logE)。

所以這種 Prim 算法實現(xiàn)的總時間復(fù)雜度是O(ElogE)?；叵胍幌?/span>Kruskal 算法，它的時間復(fù)雜度主要是給所有邊按照權(quán)重排序，也是O(ElogE)。

不過話說回來，和前文Dijkstra 算法類似，Prim 算法的時間復(fù)雜度也是可以優(yōu)化的，但優(yōu)化點在于優(yōu)先級隊列的實現(xiàn)上，和 Prim 算法本身的算法思想關(guān)系不大，所以我們這里就不做討論了，有興趣的讀者可以自行搜索。

接下來，我們實操一波，把之前用 Kruskal 算法解決的力扣題目運用 Prim 算法再解決一遍。

題目實踐

第一題是力扣第 1135 題「最低成本聯(lián)通所有城市」，這是一道標(biāo)準(zhǔn)的最小生成樹問題：

函數(shù)簽名如下：

intminimumCost(intn,int[][]connections);

每座城市相當(dāng)于圖中的節(jié)點，連通城市的成本相當(dāng)于邊的權(quán)重，連通所有城市的最小成本即是最小生成樹的權(quán)重之和。

那么解法就很明顯了，我們先把題目輸入的connections轉(zhuǎn)化成鄰接表形式，然后輸入給之前實現(xiàn)的Prim算法類即可：

publicintminimumCost(intn,int[][]connections){
//轉(zhuǎn)化成無向圖鄰接表的形式
List<int[]>[]graph=buildGraph(n,connections);
//執(zhí)行Prim算法
Primprim=newPrim(graph);

if(!prim.allConnected()){
//最小生成樹無法覆蓋所有節(jié)點
return-1;
}

returnprim.weightSum();
}

List<int[]>[]buildGraph(intn,int[][]connections){
//圖中共有n個節(jié)點
List<int[]>[]graph=newLinkedList[n];
for(inti=0;inewLinkedList<>();
}
for(int[]conn:connections){
//題目給的節(jié)點編號是從1開始的，
//但我們實現(xiàn)的Prim算法需要從0開始編號
intu=conn[0]-1;
intv=conn[1]-1;
intweight=conn[2];
//「無向圖」其實就是「雙向圖」
//一條邊表示為int[]{from,to,weight}
graph[u].add(newint[]{u,v,weight});
graph[v].add(newint[]{v,u,weight});
}
returngraph;
}

classPrim{/*見上文*/}

關(guān)于buildGraph函數(shù)需要注意兩點：

一是題目給的節(jié)點編號是從 1 開始的，所以我們做一下索引偏移，轉(zhuǎn)化成從 0 開始以便Prim類使用；

二是如何用鄰接表表示無向加權(quán)圖，前文圖論算法基礎(chǔ)說過「無向圖」其實就可以理解為「雙向圖」。

這樣，我們轉(zhuǎn)化出來的graph形式就和之前的Prim算法類對應(yīng)了，可以直接施展 Prim 算法計算最小生成樹。

再來看看力扣第 1584 題「連接所有點的最小費用」：

比如題目給的例子：

points=[[0,0],[2,2],[3,10],[5,2],[7,0]]

算法應(yīng)該返回 20，按如下方式連通各點：

函數(shù)簽名如下：

intminCostConnectPoints(int[][]points);

很顯然這也是一個標(biāo)準(zhǔn)的最小生成樹問題：每個點就是無向加權(quán)圖中的節(jié)點，邊的權(quán)重就是曼哈頓距離，連接所有點的最小費用就是最小生成樹的權(quán)重和。

所以我們只要把points數(shù)組轉(zhuǎn)化成鄰接表的形式，即可復(fù)用之前實現(xiàn)的Prim算法類：

publicintminCostConnectPoints(int[][]points){
intn=points.length;
List<int[]>[]graph=buildGraph(n,points);
returnnewPrim(graph).weightSum();
}

//構(gòu)造無向圖
List<int[]>[]buildGraph(intn,int[][]points){
List<int[]>[]graph=newLinkedList[n];
for(inti=0;inewLinkedList<>();
}
//生成所有邊及權(quán)重
for(inti=0;ifor(intj=i+1;jintxi=points[i][0],yi=points[i][1];
intxj=points[j][0],yj=points[j][1];
intweight=Math.abs(xi-xj)+Math.abs(yi-yj);
//用points中的索引表示坐標(biāo)點
graph[i].add(newint[]{i,j,weight});
graph[j].add(newint[]{j,i,weight});
}
}
returngraph;
}

classPrim{/*見上文*/}

這道題做了一個小的變通：每個坐標(biāo)點是一個二元組，那么按理說應(yīng)該用五元組表示一條帶權(quán)重的邊，但這樣的話不便執(zhí)行 Prim 算法；所以我們用points數(shù)組中的索引代表每個坐標(biāo)點，這樣就可以直接復(fù)用之前的 Prim 算法邏輯了。

到這里，Prim 算法就講完了，整個圖論算法也整的差不多了，更多精彩文章，敬請期待。