Prim(普裡姆)算法求最小生成樹的思惟及C說話實例講授。本站提示廣大學習愛好者：（Prim(普裡姆)算法求最小生成樹的思惟及C說話實例講授）文章只能為提供參考，不一定能成為您想要的結果。以下是Prim(普裡姆)算法求最小生成樹的思惟及C說話實例講授正文
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 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 5 6 6 4 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;
}
測試的成果以下：
