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

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

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

C++實(shí)現(xiàn)示例
prim.txt中的內(nèi)容:

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 //  定義兩個(gè)不直接相鄰一步到達(dá)頂點(diǎn)的距離 
#define max_vertexes 6 //  定義圖形中頂點(diǎn)的個(gè)數(shù)
 
typedef int Graph[max_vertexes][max_vertexes];// 邊上的權(quán)值
 
void prim(Graph G,int vcount,int father[])
{  
  int i,j,k;
  int lowcost[max_vertexes];//最小代價(jià)邊上的權(quán)值
  int closeset[max_vertexes],used[max_vertexes];//依附在U中的頂點(diǎn)；標(biāo)記是否已被選中
  int min;
  int result=0;//記錄最短距離權(quán)值的和
 
 
  for (i=0;i<vcoun;k++)  //初始化所有數(shù)組，把最短距離初始化為其他頂點(diǎn)到1結(jié)點(diǎn)的距離
  {
      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循環(huán)得到離結(jié)點(diǎn)最近的頂點(diǎn)j
   if ((!used[k])&&(lowcost[k]
   {
    min = lowcost[k];
    j=k;
   }
   father[j]=closeset[j]; 
   printf("%d %d\n",j+1,father[j]+1);//輸出當(dāng)前找到的結(jié)點(diǎn)，該頂點(diǎn)依附的上一個(gè)結(jié)點(diǎn)
   result=result+G[j][closeset[j]];
   used[j]=1;;//把第j個(gè)頂點(diǎn)并入了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;
 
}

測(cè)試的結(jié)果如下：

最新評(píng)論