Prim 最小生成樹

Table of content
上一頁
下一頁
上一頁
下一頁  

Prim 最小生成樹演算法是查詢圖的最小生成樹的有效方法之一。最小生成樹是一個子圖，它以最少的邊和最小的成本（分配給每條邊的權重的總和）連線主圖中存在的所有頂點。

該演算法類似於任何最短路徑演算法，從一個被設定為根的頂點開始，透過確定成本最低的相鄰邊遍歷圖中的所有頂點。

spanning_tree_of_graph

Prim 演算法

要執行 Prim 演算法，演算法接收的輸入是圖 G {V, E}，其中 V 是頂點集，E 是邊集，以及源頂點 S。圖 G 的最小生成樹作為輸出獲得。

演算法

  • 宣告一個數組 visited[] 用於儲存已訪問的頂點，首先，將任意根（例如 S）新增到 visited 陣列中。

  • 檢查最後一個已訪問頂點的相鄰頂點是否在 visited[] 陣列中。

  • 如果頂點不在 visited[] 陣列中，則比較邊的成本，並將成本最低的邊新增到輸出生成樹中。

  • 將具有最低成本邊的相鄰未訪問頂點新增到 visited[] 陣列中，並將最低成本邊新增到最小生成樹輸出中。

  • 步驟 2 和 4 對圖中所有未訪問的頂點重複執行，以獲得給定圖的完整最小生成樹輸出。

  • 計算獲得的最小生成樹的成本。

示例

  • 使用 Prim 方法（貪心演算法）查詢下面給定圖的最小生成樹，其中 S 為任意根。

minimum spanning tree

解決方案

步驟 1

建立一個 visited 陣列，將所有已訪問的頂點儲存到其中。

V = { }

任意根被指定為 S，因此在連線到 S 的所有邊中，我們需要找到成本最低的邊。

S → B = 8
V = {S, B}
s to b

步驟 2

由於 B 是最後一個已訪問的頂點，因此檢查連線到頂點 B 的成本最低的邊。

B → A = 9
B → C = 16
B → E = 14

因此，B → A 是新增到生成樹的邊。

V = {S, B, A}
b to a

步驟 3

由於 A 是最後一個已訪問的頂點，因此檢查連線到頂點 A 的成本最低的邊。

A → C = 22
A → B = 9
A → E = 11

但是 A → B 已經在生成樹中了，檢查下一個成本最低的邊。因此，A → E 被新增到生成樹中。

V = {S, B, A, E}
a to e

步驟 4

由於 E 是最後一個已訪問的頂點，因此檢查連線到頂點 E 的成本最低的邊。

E → C = 18
E → D = 3

因此，E → D 被新增到生成樹中。

V = {S, B, A, E, D}
e to d

步驟 5

由於 D 是最後一個已訪問的頂點，因此檢查連線到頂點 D 的成本最低的邊。

D → C = 15
E → D = 3

因此，D → C 被新增到生成樹中。

V = {S, B, A, E, D, C}
d to c

獲得的最小生成樹的最小成本 = 46

示例

最終程式實現了 Prim 最小生成樹問題，該問題以成本鄰接矩陣作為輸入，並列印生成樹作為輸出以及最小成本。

C C++ Java Python
#include<stdio.h>
#include<stdlib.h>
#define inf 99999
#define MAX 10
int G[MAX][MAX] = {
   {0, 19, 8},
   {21, 0, 13},
   {15, 18, 0}
};
int S[MAX][MAX], n;
int prims();
int main(){
   int i, j, cost;
   n = 3;
   cost=prims();
   printf("Spanning tree:");
   for(i=0; i<n; i++) {
      printf("\n");
      for(j=0; j<n; j++)
         printf("%d\t",S[i][j]);
   }
   printf("\nMinimum cost = %d", cost);
   return 0;
}
int prims(){
   int C[MAX][MAX];
   int u, v, min_dist, dist[MAX], from[MAX];
   int visited[MAX],ne,i,min_cost,j;

   //create cost[][] matrix,spanning[][]
   for(i=0; i<n; i++)
      for(j=0; j<n; j++) {
         if(G[i][j]==0)
            C[i][j]=inf;
         else
            C[i][j]=G[i][j];
         S[i][j]=0;
      }

   //initialise visited[],distance[] and from[]
   dist[0]=0;
   visited[0]=1;
   for(i=1; i<n; i++) {
      dist[i] = C[0][i];
      from[i] = 0;
      visited[i] = 0;
   }
   min_cost = 0; //cost of spanning tree
   ne = n-1; //no. of edges to be added
   while(ne > 0) {

      //find the vertex at minimum distance from the tree
      min_dist = inf;
      for(i=1; i<n; i++)
         if(visited[i] == 0 && dist[i] < min_dist) {
            v = i;
            min_dist = dist[i];
         }
      u = from[v];

      //insert the edge in spanning tree
      S[u][v] = dist[v];
      S[v][u] = dist[v];
      ne--;
      visited[v]=1;

      //updated the distance[] array
      for(i=1; i<n; i++)
         if(visited[i] == 0 && C[i][v] < dist[i]) {
            dist[i] = C[i][v];
            from[i] = v;
         }
      min_cost = min_cost + C[u][v];
   }
   return(min_cost);
}

輸出

Spanning tree:
0	0	8	
0	0	13	
8	13	0	
Minimum cost = 26

#include<iostream>
#define inf 999999
#define MAX 10
using namespace std;
int G[MAX][MAX] = {
   {0, 19, 8},
   {21, 0, 13},
   {15, 18, 0}
};
int S[MAX][MAX], n;
int prims();
int main(){
   int i, j, cost;
   n = 3;
   cost=prims();
   cout <<"Spanning tree:";
   for(i=0; i<n; i++) {
      cout << endl;
      for(j=0; j<n; j++)
         cout << S[i][j] << " ";
   }
   cout << "\nMinimum cost = " << cost;
   return 0;
}
int prims(){
   int C[MAX][MAX];
   int u, v, min_dist, dist[MAX], from[MAX];
   int visited[MAX],ne,i,min_cost,j;

   //create cost matrix and spanning tree
   for(i=0; i<n; i++)
      for(j=0; j<n; j++) {
         if(G[i][j]==0)
            C[i][j]=inf;
         else
            C[i][j]=G[i][j];
         S[i][j]=0;
      }

   //initialise visited[],distance[] and from[]
   dist[0]=0;
   visited[0]=1;
   for(i=1; i<n; i++) {
      dist[i] = C[0][i];
      from[i] = 0;
      visited[i] = 0;
   }
   min_cost = 0; //cost of spanning tree
   ne = n-1; //no. of edges to be added
   while(ne > 0) {

      //find the vertex at minimum distance from the tree
      min_dist = inf;
      for(i=1; i<n; i++)
         if(visited[i] == 0 && dist[i] < min_dist) {
            v = i;
            min_dist = dist[i];
         }
      u = from[v];

      //insert the edge in spanning tree
      S[u][v] = dist[v];
      S[v][u] = dist[v];
      ne--;
      visited[v]=1;

      //updated the distance[] array
      for(i=1; i<n; i++)
         if(visited[i] == 0 && C[i][v] < dist[i]) {
            dist[i] = C[i][v];
            from[i] = v;
         }
      min_cost = min_cost + C[u][v];
   }
   return(min_cost);
}

輸出

Spanning tree:
0 0 8 
0 0 13 
8 13 0 
Minimum cost = 26

public class prims {
   static int inf = 999999;
   static int MAX = 10;
   static int G[][] = {
       {0, 19, 8},
       {21, 0, 13},
       {15, 18, 0}
   };
   static int S[][] = new int[MAX][MAX];
   static int n;
   public static void main(String args[]) {
      int i, j, cost;
      n = 3;
      cost=prims();
      System.out.print("Spanning tree: ");
      for(i=0; i<n; i++) {
         System.out.println();
         for(j=0; j<n; j++)
            System.out.print(S[i][j] + " ");
      }
      System.out.println("\nMinimum cost = " + cost);
   }
   static int prims() {
      int C[][] = new int[MAX][MAX];
      int u, v = 0, min_dist;
      int dist[] = new int[MAX];
      int from[] = new int[MAX];
      int visited[] = new int[MAX];
      int ne,i,min_cost,j;
      //create cost matrix and spanning tree
      for(i=0; i<n; i++)
         for(j=0; j<n; j++) {
            if(G[i][j]==0)
               C[i][j]=inf;
            else
               C[i][j]=G[i][j];
            S[i][j]=0;
         }
      //initialise visited[],distance[] and from[]
      dist[0]=0;
      visited[0]=1;
      for(i=1; i<n; i++) {
         dist[i] = C[0][i];
         from[i] = 0;
         visited[i] = 0;
      }
      min_cost = 0; //cost of spanning tree
      ne = n-1; //no. of edges to be added
      while(ne > 0) {
         //find the vertex at minimum distance from the tree
         min_dist = inf;
         for(i=1; i<n; i++)
            if(visited[i] == 0 && dist[i] < min_dist) {
               v = i;
               min_dist = dist[i];
            }
         u = from[v];
         //insert the edge in spanning tree
         S[u][v] = dist[v];
         S[v][u] = dist[v];
         ne--;
         visited[v]=1;
         //updated the distance[] array
         for(i=1; i<n; i++)
            if(visited[i] == 0 && C[i][v] < dist[i]) {
               dist[i] = C[i][v];
               from[i] = v;
            }
         min_cost = min_cost + C[u][v];
      }
      return(min_cost);
   }
}

輸出

Spanning tree: 
0 0 8 
0 0 13 
8 13 0 
Minimum cost = 26

inf = 999999
MAX = 10
G = [
    [0, 19, 8],
    [21, 0, 13],
    [15, 18, 0]
]
S = [[0 for _ in range(MAX)] for _ in range(MAX)]
n = 3
def main():
    global n
    cost = prims()
    print("Spanning tree: ")
    for i in range(n):
        print()
        for j in range(n):
            print(S[i][j], end=" ")
    print("\nMinimum cost =", cost)
def prims():
    global n
    C = [[0 for _ in range(MAX)] for _ in range(MAX)]
    u, v = 0, 0
    min_dist = 0
    dist = [0 for _ in range(MAX)]
    from_ = [0 for _ in range(MAX)]
    visited = [0 for _ in range(MAX)]
    ne = 0
    min_cost = 0
    i = 0
    j = 0
    for i in range(n):
        for j in range(n):
            if G[i][j] == 0:
                C[i][j] = inf
            else:
                C[i][j] = G[i][j]
            S[i][j] = 0
    dist[0] = 0
    visited[0] = 1
    for i in range(1, n):
        dist[i] = C[0][i]
        from_[i] = 0
        visited[i] = 0
    min_cost = 0
    ne = n - 1
    while ne > 0:
        min_dist = inf
        for i in range(1, n):
            if visited[i] == 0 and dist[i] < min_dist:
                v = i
                min_dist = dist[i]
        u = from_[v]
        S[u][v] = dist[v]
        S[v][u] = dist[v]
        ne -= 1
        visited[v] = 1
        for i in range(n):
            if visited[i] == 0 and C[i][v] < dist[i]:
                dist[i] = C[i][v]
                from_[i] = v
        min_cost += C[u][v]
    return min_cost
#calling  the main() method
main()

輸出

Spanning tree: 

0 0 8 
0 0 13 
8 13 0 
Minimum cost = 26
列印頁面
上一頁
下一頁
廣告