Prim演算法 - tw511教學網

Prim演算法用於從圖中查詢最小生成樹。Prim演算法找到包括圖的每個頂點的邊的子集，使得邊的權重之和可以最小化。

Prim演算法從單個節點開始，並在每一步探索所有相鄰節點的所有連線邊緣。選擇了具有最小權重的邊緣在圖表中沒有引起迴圈。

演算法如下 -

第1步：選擇一個起始頂點
第2步：重複第3步和第4步，直到有條紋頂點
第3步：選擇連線樹頂點和具有最小權重的邊緣頂點的邊`e`。
第4步：將選定的邊和頂點新增到最小生成樹`T`。
[迴圈結束]
第5步：退出

範例：

使用prim演算法構造下圖中給出的圖的最小生成樹。

解決方案

第1步：選擇一個起始頂點B。
第2步：新增與A相鄰的頂點，連線頂點的邊用虛線表示。
第3步：選擇所有權重最小的邊緣，即BD並將其新增到MST。新增D的相鄰頂點，即C和E。
第4步：選擇所有權重最小的邊緣，在這種情況下，邊緣DE和CD是這樣的邊緣。將它們新增到MST並探索C的相鄰，即E和A。
第5步：選擇具有最小重量的邊緣，即CA。不能選擇CE，因為它會導致圖中的迴圈。

在第4步中產生的圖形是上圖中所示的圖形的最小生成樹。

MST的成本將按以下方式計算：

成本(MST)= 4 + 2 + 1 + 3 = 10 個單位。

C語言實現範例程式碼

#include <stdio.h>  
#include <limits.h>  
#define vertices 5  

int minimum_key(int k[], int mst[])  
{  
   int minimum  = INT_MAX, min,i;  

   for (i = 0; i < vertices; i++)  
     if (mst[i] == 0 && k[i] < minimum )  
         minimum  = k[i], min = i;  

   return min;  
}  


void prim(int g[vertices][vertices])  
{  
     int parent[vertices];   
     int k[vertices];     
     int mst[vertices];    
     int i, count,u,v;   
     for (i = 0; i < vertices; i++)  
        k[i] = INT_MAX, mst[i] = 0;  

     k[0] = 0;       
     parent[0] = -1;   

     for (count = 0; count < vertices-1; count++)  
     {  

        u = minimum_key(k, mst);  
      mst[u] = 1;  

        for (v = 0; v < vertices; v++)  

          if (g[u][v] && mst[v] == 0 && g[u][v] <  k[v])  
             parent[v]  = u, k[v] = g[u][v];  
     }  

    for (i = 1; i < vertices; i++)  
      printf("%d  %d    %d \n", parent[i], i, g[i][parent[i]]);  
}  


void main()  
{  
   int g[vertices][vertices] = {{3, 2, 1, 9, 0},  
                      {5, 1, 2, 10, 4},  
                      {0, 4, 1, 0, 9},  
                      {8, 10, 0, 2, 10},  
                      {1, 6, 8, 11, 0},  
                     };  

    prim(g);  
}

執行上面範例程式碼，得到以下結果 -