注明：本部落格參考《資料結構教程》第4版
（一）知識準備
在開始學習Prim算法之前，我們需要對圖有一定的了解，且知道圖的存儲方式（本部落格基于無向圖和鄰接矩陣的知識），同時我們要了解什麼是生成樹？一個連通圖的生成樹是該連通圖的一個極小連通子圖，它是含有圖的全部頂點，但隻有構成一棵樹的（n-1）條邊，而最小生成樹則是在生成樹的基礎上，要求樹的（n-1）條邊的權值之和是最小的。由此可以總結構造最小生成樹的要求有：（1）必須隻使用該圖中的邊來構造最小生成樹；（2）必須使用且僅使用（n-1）條邊來連接配接圖中的n個頂點；（3）不能使用産生回路的邊；（4）要求樹的（n-1）條邊的權值之和是最小的。
（二）算法初識
接着開始我們的Prim算法的學習！首先我們先來認識下Prim算法的基礎認識（後面我們會更加嚴謹的給出其定義與推算過程）：通過選點來構造最小生成樹，每次（第一次
可随意挑選）從中挑選目前最适合的（即選倆點的權值最小的，使構造的目前生成樹最小）點來構造最小生成樹。
（三）算法執行個體示範
首先讓我們來看一個example。如下圖所示，圖a是一個連通圖（右圖是圖a對應的鄰接矩陣，假設圖中的邊的權值大于0），我們現在基于該圖來示範Prim算法的過程。
我們選擇一個起點，然後在與起點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。假設起點是0節點，與0節點相連且未被選的節點是{1,2,3}，分别對應的權值是{6,1,5}，可見目前最小的權值1，權值最小的節點就是2節點，是以将2節點和0-2的邊添加入生成樹，如圖b所示。
接着我們在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。目前已選節點是0,2節點，與已選節點相連且未被選的節點有{1,3,4,5}，分别對應的權值是{（6,5），（5,5），6,4,}，可見目前最小的權值4，權值最小的節點就是5節點，是以将5節點和2-5的邊添加入生成樹，如圖c所示。（其實在程式設計時，我們隻需記錄與更新目前較小的那個權值，如與{1,3,4,5}對應的權值我們隻需記錄{5,5,6,4}，當然我們也需利用了另一個數組來加以差別目前權值對應的連接配接點，如目前權值{5,5,6,4}所對應的連接配接點就是{2,0,2,2}）
接着我們繼續在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。目前已選節點是0,2,5節點，與已選節點相連且未被選的節點有{1,3,4}，分别對應的權值是{（6,5），（2,5,5），（6,6）,}（其實目前我們可隻記錄{5,2,6}，同時記錄其對應的連接配接點分别是{2,5,2}），可見目前最小的權值2，權值最小的節點就是3節點，是以将3節點和5-3的邊添加入生成樹，如圖d所示。
接着我們依照上一次的步驟繼續在與已選節點相連且未被選的節點中選擇一個權值最小的節點，将該節點與其相連邊添加入生成樹。如圖e，f所示。最終圖f就是我們通過Prim算法得到的最小生成樹了。
（四）算法概念
現在我們給出Prim的嚴謹概念：Prim算法是一種構造性算法。假設G=（V,E）是一個具有n個頂點的帶權連通無向圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則由G構造從起始頂點v出發的最小生成樹T的步驟如下：
（1）初始化U={v},以v到其他頂點的所有邊為候選邊；
（2）重複以下步驟（n-1）次，使得其他（n-1）個頂點被加入到U中：
1.從侯選邊中挑選權值最小的邊加入TE，設該邊在V-U中的頂點是k，将k加入U中；
2.考察目前V-U中所有頂點j，修改侯選邊，若邊（k，j）的權值小于原來和頂點j關聯的侯選邊，則用邊（k，j）取代後者作為侯選邊
現在我們可以來程式設計實作Prim算法啦！
（五）程式設計實作
首先，在動手程式設計之前我們需要了解我們考慮實作Prim算法的一些相關的東西。
第一個考慮的便是傳入的參數，第一個參數就是無向圖的資訊（這裡我們用鄰接矩陣MGraph來存儲），第二個參數是起點。下面給出鄰接矩陣的結構體。
//鄰接矩陣的資料類型
#define MAXV 50 //最大頂點數
typedef struct
{
int no;//頂點編号
//InfoType info;//頂點的其他資訊
}VertexType;//頂點類型
typedef struct
{
int edges[MAXV][MAXV];//鄰接矩陣的邊數組
int n, e;//頂點數，邊數
VertexType vexs[MAXV];//存放頂點資訊
}MGraph;//圖鄰接矩陣類型
#define INF 32767//表示無窮大
下面來介紹實作Prim算法的一些重要的變量或結構。
為了便于選中目前權值最小的邊的節點，需要建立兩個數組closest和lowcost，對于某個未選中的節點j，lowcost[j]存儲的是節點j與目前已選節點相連的最小權值（lowcost[j]==0表示節點j已被選），closest[j]存儲lowcost[j]對應的連接配接點，如下圖所示。
按照上面例子（即按圖a得到最小生成樹），其求解過程中lowcost數組和closest數組的變化，如下圖所示（希望讀者結合下面的程式代碼來分析這兩個數組）。
現在我們可以動手程式設計了！代碼如下：
void Prim(MGraph g, int v)//普利姆算法（參數：鄰接矩陣，起點（即第一個生成的點，可随便取））
{
int lowcost[MAXV], closest[MAXV], i, min, j, k;
/***初始化lowcost數組，closest數組(即從起點開始設定lowcost數組，closest數組相應的值，以便後續生成使用)***/
for (i = 0; i < g.n; i++)//賦初值，即将closest數組都賦為第一個節點v，lowcost數組賦為第一個節點v到各節點的權重
{
closest[i] = v;
lowcost[i] = g.edges[v][i];//g.edges[v][i]的值指的是節點v到i節點的權重
}
/**********************************開始生成其他的節點*********************************/
for (i = 1; i < g.n; i++)//接下來找剩下的n-1個節點（g.n是圖的節點個數）
{
/*****找到一個節點，該節點到已選節點中的某一個節點的權值是目前最小的*****/
min = INF;//INF表示正無窮（每查找一個節點，min都會重新更新為INF，以便擷取目前最小權重的節點）
for (j = 0; j < g.n; j++)//周遊所有節點
{
if (lowcost[j] != 0 && lowcost[j] < min)//若該節點還未被選且權值小于之前周遊所得到的最小值
{
min = lowcost[j];//更新min的值
k = j;//記錄目前最小權重的節點的編号
}
}
/****************輸出被連接配接節點與連接配接節點，以及它們的權值***************/
printf("邊(%d,%d)權為:%d\n", closest[k], k, min);
/***********更新lowcost數組，closest數組，以便生成下一個節點************/
lowcost[k] = 0;//表明k節點已被選了(作标記)
//選中一個節點完成連接配接之後，作數組相應的調整
for (j = 0; j < g.n; j++)//周遊所有節點
{
/* if語句條件的說明：
* （1）g.edges[k][j] != 0是指k！=j，即跳過自身的節點
* （2）g.edges[k][j]是指剛被選的節點k到節點j的權重，lowcost[j]是指之前周遊的所有節點與j節點的最小權重。若g.edges[k][j] < lowcost[j],則說明目前剛被選的節點k與節點j之間存在更小的權重，則需要更新
* （3）有人會問：為什麼隻跳過掉自身的節點（即k==j），而不跳過所有的已選節點？當然我們可以在if語句條件中增加跳過所有的已選節點的條件（即lowcost[j] == 0），而在本程式中我們隻跳過了自身的節點？（注意：我們假設圖中的邊的權值大于0）但其實不是，g.edges[k][j] < lowcost[j]條件已包含跳過所有的已選節點，原因是在鄰接矩陣中權值為0是最小的，即g.edges[k][j]>=0，而已選節點滿足lowcost[j] == 0，則已選節點j是不滿足g.edges[k][j] < lowcost[j]，則會被跳過
*/
if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j])
{
//更新lowcost數組，closest數組
lowcost[j] = g.edges[k][j];//更新權重，使其目前最小
closest[j] = k;//進入到該if語句裡，說明剛選的節點k與目前節點j有更小的權重，則closest[j]的被連接配接節點需作修改為k
}
}
}
}
Prim算法中有兩重for循環，是以時間複雜度為O(n^2)，其中n為圖的頂點個數。
本人是一個喜歡算法的新手，本部落格以自己的了解簡要的介紹了Prim算法，若本部落格有錯誤需要修改的或對排版風格有要改進的等建議，請留言或發郵件給我。寫部落格是一個互相學習的過程，期待收到您的建議！記住，不要沮喪，好好學習，天天向上！共勉！