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

1135. 最低成本聯通所有城市（中等）1584. 連接所有點的最小費用（中等）

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

1、圖論算法基礎

2、二分圖判定算法

3、環檢測和拓撲排序算法

4、Dijkstra 最短路徑算法

5、Union Find 并查集算法

6、Kruskal 最小生成樹算法

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

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

對比 Kruskal 算法

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

1、這些邊組成的是一棵樹（樹和圖的區別在于不能包含環）。

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

3、這些邊的權重之和要盡可能小。

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

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

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

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

如果一條邊的兩個節點已經是連通的，則這條邊會使樹中出現環；如果最后的連通分量總數大于 1，則說明形成的是「森林」而不是一棵「樹」。

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

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

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

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

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

切分定理

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

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

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

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

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

對于任意一種「切分」，其中權重最小的那條「橫切邊」一定是構成最小生成樹的一條邊。

這應該很容易證明，如果一幅加權無向圖存在最小生成樹，假設下圖中用綠色標出來的邊就是最小生成樹：

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

你會發現，任選一條藍色的「橫切邊」都可以將這兩棵子樹連接起來，構成一棵生成樹。

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

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

關于切分定理，你也可以用反證法證明：

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

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

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

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

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

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

Prim 算法實現

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

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

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

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

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

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

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

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

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

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

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

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

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

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

是可以的，因為我們發現：

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

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

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

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

當然，細心的讀者肯定發現了，cut({A, B})的橫切邊和cut({C})的橫切邊中BC邊重復了。

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

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

很簡單，用一個優先級隊列存儲這些橫切邊，就可以動態計算權重最小的橫切邊了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

題目實踐

第一題是力扣第 1135 題「最低成本聯通所有城市」，這是一道標準的最小生成樹問題：

函數簽名如下：

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

每座城市相當于圖中的節點，連通城市的成本相當于邊的權重，連通所有城市的最小成本即是最小生成樹的權重之和。

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

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

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

returnprim.weightSum();
}

List<int[]>[]buildGraph(intn,int[][]connections){
//圖中共有n個節點
List<int[]>[]graph=newLinkedList[n];
for(inti=0;inewLinkedList<>();
}
for(int[]conn:connections){
//題目給的節點編號是從1開始的，
//但我們實現的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{/*見上文*/}

關于buildGraph函數需要注意兩點：

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

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

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

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

比如題目給的例子：

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

算法應該返回 20，按如下方式連通各點：

函數簽名如下：

intminCostConnectPoints(int[][]points);

很顯然這也是一個標準的最小生成樹問題：每個點就是無向加權圖中的節點，邊的權重就是曼哈頓距離，連接所有點的最小費用就是最小生成樹的權重和。

所以我們只要把points數組轉化成鄰接表的形式，即可復用之前實現的Prim算法類：

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

//構造無向圖
List<int[]>[]buildGraph(intn,int[][]points){
List<int[]>[]graph=newLinkedList[n];
for(inti=0;inewLinkedList<>();
}
//生成所有邊及權重
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中的索引表示坐標點
graph[i].add(newint[]{i,j,weight});
graph[j].add(newint[]{j,i,weight});
}
}
returngraph;
}

classPrim{/*見上文*/}

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

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