文章目錄

• 1 最小生成樹（Minimum Spanning Tree,MST）
• 2 Prim算法
• • 2.1 簡介
  • 2.2 具體步驟
  • 2.3 算法示例圖
  • 2.4 算法實現
  • 2.5 算法分析
  • 2.6 測試

1 最小生成樹（Minimum Spanning Tree,MST）

在一給定的無向圖$G=(V,E)$ 中，$(u,v)$代表連接頂點$u$ 與頂點 $v$ 的邊，而 $w(u,v)$ 代表此邊的權重，若存在 $T$ 為 $E$ 的子集且為無循環圖，使得 $w(T)$ 最小，則此 $T$ 為 $G$ 的最小生成樹，因為$T$是由圖$G$產生的。

最小生成樹其實是最小權重生成樹的簡稱。我們稱求取該生成樹的問題成為最小生成樹問題。一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小于或者等于其它生成樹的邊的權值之和。廣義上而言，對于非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的并被稱為最小生成森林。以有線電視電纜的架設為例，若只能沿著街道布線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使布線成本最低。

如圖，這個是一個平面圖，圖中黑色線描述的就是最小生成樹，它的權值之和小于其他的生成樹。

那么，我們如何來求最小生成樹呢，由最小生成樹的定義我們可以知道構建最小生成樹是可以利用貪心算法去實現的，我們接下來介紹的兩種算法也都是利用貪心算法去求得$MST$的。因為貪心算法的策略就是在每一步盡可能多的選擇中選擇最優的，在當前看是最好的選擇，這種策略雖然一般不能在全局中尋找到最優解，但是對于最小生成樹問題來說，它的確可以找到一顆權重最小的樹。

2 Prim算法

2.1 簡介

普里姆算法（Prim’s algorithm），圖論中的一種算法，可在加權連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權值之和亦為最小。該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克發現；并在1957年由美國計算機科學家羅伯特·普里姆獨立發現；1959年，艾茲格·迪科斯徹再次發現了該算法。因此，在某些場合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆－亞爾尼克算法。（來源于維基百科）

2.2 具體步驟

Prim算法是利用貪心算法實現的，我們確定根節點，從這個結點出發。普里姆算法按照以下步驟逐步擴大樹中所含頂點的數目，直到遍及連通圖的所有頂點。下面描述我們假設$N=(V,E)$是連通網，$TE$是$N$上最小生成樹中邊的集合。

? ① $U=\{u_0\}(u_0\in V),TE=\{\}$。

? ② 在所有$u\in U,v\in (V?U)$的邊$(u,v)\in E$找到一條權值最小的邊$(u_0,v_0)$并入集合$TE$，同時$v_0$并入集合$U$。

? ③ 重復②步驟，知道$U=V$為止。

此時$TE$中必有$n?1$條邊，則$T=(V,TE)$即為我們求得的$N$的最小生成樹。

2.3 算法示例圖

2.4 算法實現

我們如果對Dijkstra算法很熟悉的話，Prim算法也很好實現了，它們都是利用了一樣的思路，但卻不相同。我們用利用$lowcost$數組來表示到集合中最近的距離，用$closest$數組來表示最小生成樹的邊。怎么來表示呢？我們用頂點來形容邊，也就是說我們要求的就是$closet$數組。其中$closest[i]$表示的值就是與$i$頂點相鄰邊的頂點序號。具體看代碼（附帶打印最小生成樹代碼）。

/* *郵箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何問題請私信我或評論區留言，謝謝支持。 * */ #include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i為循環變量，a為初始值，n為界限值，遞增 #define per(i,a,n) for (int i=a;i>=n;i--)//i為循環變量， a為初始值，n為界限值，遞減。 #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//無窮大 const int maxn = 1e3;//最大值。 typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; //*******************************分割線，以上為自定義代碼模板***************************************//int n,m;//圖的大小和邊數。 int graph[maxn][maxn];//圖 int lowcost[maxn],closest[maxn];//lowcost[i]表示i到距離集合最近的距離，closest[i]表示i與之相連邊的頂點序號。 int sum;//計算最小生成樹的權值總和。 void Prim(int s){//初始化操作，獲取基本信息。rep(i,1,n){if(i==s)lowcost[i]=0;elselowcost[i]=graph[s][i];closest[i]=s;}int minn,pos;//距離集合最近的邊，pos代表該點的終邊下標。sum=0;rep(i,1,n){minn=inf;rep(j,1,n){//找出距離點集合最近的邊。if(lowcost[j]!=0&&lowcost[j]<minn){minn=lowcost[j];pos=j;}}if(minn==inf)break;//說明沒有找到。sum+=minn;//計算最小生成樹的權值之和。lowcost[pos]=0;//加入點集合。rep(j,1,n){//由于點集合中加入了新的點，我們要去更新。if(lowcost[j]!=0&&graph[pos][j]<lowcost[j]){lowcost[j]=graph[pos][j];closest[j]=pos;//改變與頂點j相連的頂點序號。}}}cout<<sum<<endl;//closest數組就是我們要的最小生成樹。它代表的就是邊。 } void print(int s){//打印最小生成樹。int temp;rep(i,1,n){//等于s自然不算，故除去這個為n-1條邊。if(i!=s){temp=closest[i];cout<<temp<<"->"<<i<<"邊權值為："<<graph[temp][i]<<endl;}} } int main(){//freopen("in.txt", "r", stdin);//提交的時候要注釋掉IOS;while(cin>>n>>m){memset(graph,inf,sizeof(graph));//初始化。int u,v,w;//臨時變量。rep(i,1,m){cin>>u>>v>>w;//視情況而論，我這里以無向圖為例。graph[u][v]=graph[v][u]=w;}//任取根結點，我這里默認取1.Prim(1);print(1);//打印最小生成樹。}return 0; }

2.5 算法分析

對于此算法，我們圖中有$n$個頂點，則第一個進行初始化的循環語句的頻度為$n$,第二個循環語句的頻度為$n$，但其中第二個循環中有兩個內循環：第一個是在$lowcost$中求最小值，其頻度為$n$，第二個是重新選擇具有最小權值的邊，頻度為$n$，由此我們可知Prim算法的時間復雜度為$O(n^2)$，與圖中的邊數無關，故十分適合于稠密圖。

2.6 測試

我們用示例來測試：

7 11 1 2 7 1 4 5 2 4 9 2 3 8 2 5 7 4 5 15 4 6 6 6 7 11 5 6 8 5 7 9 3 5 5

測試結果如圖：

總結

以上是生活随笔為你收集整理的Prim算法简易教程（~简单易懂，附最详细注释代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。