Prim 算法思想：
從任意一頂點 v0 開始選擇其最近頂點 v1 構成樹 T1，再連接與 T1 最近頂點 v2 構成樹 T2， 如此重復直到所有頂點均在所構成樹中為止。
最小生成樹（MST）：權值最小的生成樹。
生成樹和最小生成樹的應用：要連通n個城市需要n－1條邊線路。可以把邊上的權值解釋為線路的造價。則最小生成樹表示使其造價最小的生成樹。
構造網的最小生成樹必須解決下面兩個問題：
1、盡可能選取權值小的邊，但不能構成回路；
2、選取n－1條恰當的邊以連通n個頂點；
MST性質：假設G＝(V,E)是一個連通網，U是頂點V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。
prim算法假設G＝(V，E)是連通的，TE是G上最小生成樹中邊的集合。算法從U＝{u0}（u0∈V）、TE＝{}開始。重復執行下列操作：
在所有u∈U，v∈V－U的邊(u，v)∈E中找一條權值最小的邊(u0,v0)并入集合TE中，同時v0并入U，直到V＝U為止。
此時，TE中必有n-1條邊，T=(V，TE)為G的最小生成樹。
 Prim算法的核心:始終保持TE中的邊集構成一棵生成樹。
注意：prim算法適合稠密圖，其時間復雜度為O(n^2)，其時間復雜度與邊得數目無關，而kruskal算法的時間復雜度為O(eloge)跟邊的數目有關，適合稀疏圖。
舉個簡單的例子來說明具體的實現方法：

G:圖，用鄰接矩陣表示
vcount:表示圖的頂點個數
max_vertexes:圖最大節點數
infinity:為無窮大
數組存儲從0開始
由于最小生成樹包含每個頂點，那么頂點的選中與否就可以直接用一個數組來標記used[max_vertexes];（我們這里直接使用程序代碼中的變量定義，這樣也易于理解）；當選中一個數組的時候那么就標記，現在就有一個問題，怎么來選擇最小權值邊，注意這里最小權值邊是有限制的，邊的一個頂點一定在已選頂點中，另一個頂點當然就是在未選頂點集合中了。我最初的一個想法就是窮搜了，就是在一個集合中選擇一個頂點，來查找到另一個集合中的最小值，這樣雖然很易于理解，但是很明顯效率不是很高，在嚴蔚敏的《數據結構》上提供了一種比較好的方法來解決：設置兩個輔助數組lowcost[max_vertexes]和closeset[max_vertexes]，lowcost[max_vertexes]數組記錄從U到V－U具有最小代價的邊。對于每個頂點v∈V－U,closedge[v], closeset[max_vertexes]記錄了該邊依附的在U中的頂點。

Prim 算法步驟：
T0 存放生成樹的邊，初值為空
輸入加權圖的帶權鄰接矩陣 C = (Cij)n×n (兩點間無邊相連則其大小為無窮)
為每個頂點 v 添加一屬性 L(v) ：表 v 到 T0 的最小直接距離
（1) T0←∅, V1={v0}, C(T0)=0
（2) 對任意v ∈ V，L(v)←C(v, v0)
（3) If V==V1 then stop else goto next.
（4) 在 V-V1 中找點 u 使 L(u) =min{ L(v) | v ∈ (V − V1 )},記 V1 中與 u 相鄰點為 w.
（5) T0←T0∪{(u, w)}, C(T0) ←C(T0)+C(u, w), V1←V1∪{u}
（6) 對任意v ∈ (V − V1 ) if C(v, u)<L(v) then L(v) = C(v, u) else L(v)不變。
（7) Go to 3.

C++實現示例
prim.txt中的內容:

1 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 45 6 64 6 2

 
程序代碼：

#include<stdo.h>#include<string.h>#include <stdlib.h> #define infinity 1000000 //  定義兩個不直接相鄰一步到達頂點的距離 #define max_vertexes 6 //  定義圖形中頂點的個數 typedef int Graph[max_vertexes][max_vertexes];// 邊上的權值 void prim(Graph G,int vcount,int father[]){    int i,j,k;  int lowcost[max_vertexes];//最小代價邊上的權值  int closeset[max_vertexes],used[max_vertexes];//依附在U中的頂點；標記是否已被選中  int min;  int result=0;//記錄最短距離權值的和    for (i=0;i<vcoun;k++)  //初始化所有數組，把最短距離初始化為其他頂點到1結點的距離  {      lowcost[i]=G[0][i];       closeset[i]=0;      used[i]=0;     father[i]=-1;     }    used[0]=1;      for (i=1;i<=vcount-1;i++)     {      j=0;    min = infinity;         for (k=1;k<count;k++) //for循環得到離結點最近的頂點j   if ((!used[k])&&(lowcost[k]   {    min = lowcost[k];    j=k;   }   father[j]=closeset[j];    printf("%d %d/n",j+1,father[j]+1);//輸出當前找到的結點，該頂點依附的上一個結點   result=result+G[j][closeset[j]];   used[j]=1;;//把第j個頂點并入了U中     for (k=1;k           if (!used[k]&&(G[j][k]保留到k的最短路徑     {      lowcost[k]=G[j][k];         closeset[k]=j;    }     }  printf("%d",result);}        int main(){  FILE *fr;  int i,j,weight;  Graph G;  int fatheer[max_vertexes];  for(i=0; i<max_vertexes;i++)  for(j=0; j<max_vertexer;i++)  G[i][j] = infinity;  fr = fopen("prim.txt","r");  if(!fr)  {   printf("fopen failed/n");   exit(1);  }  while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)  {   G[i-1][j-1] = weight;   G[j-1][i-1] = weight;  }   prim(G,max_vertexes,fatheer);  return 0; }

測試的結果如下：