克魯斯卡爾最小生成樹演算法

Table of content
上一頁
下一頁

克魯斯卡爾最小生成樹演算法是尋找圖的最小生成樹的有效方法之一。最小生成樹是一個子圖，它以最少的邊和最小成本（分配給每條邊的權重之和）連線主圖中的所有頂點。

該演算法首先從圖的森林開始——定義為僅包含主圖頂點的子圖——然後新增成本最低的邊，直到建立最小生成樹，而不會在圖中形成環。

克魯斯卡爾演算法比普里姆演算法更容易實現，但複雜度更高。

克魯斯卡爾演算法

克魯斯卡爾演算法的輸入是圖 G {V, E}，其中 V 是頂點集，E 是邊集，以及源頂點 S，輸出是圖 G 的最小生成樹。

演算法

  • 將圖中所有邊按升序排序，並將其儲存在陣列edge[] 中。

  • 在平面上構造圖的森林，其中包含所有頂點。

  • 從edge[]陣列中選擇成本最低的邊，並將其新增到圖的森林中。透過將訪問過的頂點新增到visited[]陣列中來標記已訪問的頂點。

  • 重複步驟2和3，直到所有頂點都被訪問，並且圖中沒有形成任何環。

  • 當所有頂點都被訪問時，最小生成樹就形成了。

  • 計算形成的輸出生成樹的最小成本。

示例

使用克魯斯卡爾演算法為下面給出的圖構造最小生成樹：

kruskals_algorithm_graph

解決方案

第一步，將給定圖中的所有邊按升序排序，並將值儲存在陣列中。

邊 B→D A→B C→F F→E B→C G→F A→G C→D D→E C→G
成本 5 6 9 10 11 12 15 17 22 25

然後，在一個平面上構造給定圖的森林。

graph_on_single_plane

從排序的邊成本列表中，選擇成本最低的邊，並將其新增到輸出圖的森林中。

B → D = 5
Minimum cost = 5
Visited array, v = {B, D}
sorted_edge_costs

類似地，下一個成本最低的邊是 B → A = 6；因此，我們將其新增到輸出圖中。

Minimum cost = 5 + 6 = 11
Visited array, v = {B, D, A}
graph_b_to_a

下一個成本最低的邊是 C → F = 9；將其新增到輸出圖中。

Minimum Cost = 5 + 6 + 9 = 20
Visited array, v = {B, D, A, C, F}
graph_c_to_f

下一個要新增到輸出圖的邊是 F → E = 10。

Minimum Cost = 5 + 6 + 9 + 10 = 30
Visited array, v = {B, D, A, C, F, E}
output_graph_e_to_f

來自成本最低陣列的下一條邊是 B → C = 11，因此我們將其新增到輸出圖中。

Minimum cost = 5 + 6 + 9 + 10 + 11 = 41
Visited array, v = {B, D, A, C, F, E}
least_cost_array

要新增到輸出圖的來自成本最低陣列的最後一條邊是 F → G = 12。

Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53
Visited array, v = {B, D, A, C, F, E, G}
output_graph_f_to_g

獲得的結果是給定圖的最小生成樹，成本 = 53。

示例

最終程式實現了克魯斯卡爾最小生成樹問題，該問題將成本鄰接矩陣作為輸入，並列印最短路徑以及最小成本作為輸出。

C C++ Java Python
#include <stdio.h>
#include <stdlib.h>
const int inf = 999999;
int k, a, b, u, v, n, ne = 1;
int mincost = 0;
int cost[3][3] = {{0, 10, 20},{12, 0,15},{16, 18, 0}};
int  p[9] = {0};
int applyfind(int i)
{
    while(p[i] != 0)
        i=p[i];
    return i;
}
int applyunion(int i,int j)
{
    if(i!=j) {
        p[j]=i;
        return 1;
    }
    return 0;
}
int main()
{
    n = 3;
    int i, j;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (cost[i][j] == 0) {
                cost[i][j] = inf;
            }
        }
    }
    printf("Minimum Cost Spanning Tree: \n");
    while(ne < n) {
        int min_val = inf;
        for(i=0; i<n; i++) {
            for(j=0; j <n; j++) {
                if(cost[i][j] < min_val) {
                    min_val = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = applyfind(u);
        v = applyfind(v);
        if(applyunion(u, v) != 0) {
            printf("%d -> %d\n", a, b);
            mincost +=min_val;
        }
        cost[a][b] = cost[b][a] = 999;
        ne++;
    }
    printf("Minimum cost = %d",mincost);
    return 0;
}

輸出

Minimum Cost Spanning Tree: 
0 -> 1
1 -> 2
Minimum cost = 25

#include <iostream>
using namespace std;
const int inf = 999999;
int k, a, b, u, v, n, ne = 1;
int mincost = 0;
int cost[3][3] = {{0, 10, 20}, {12, 0, 15}, {16, 18, 0}};
int p[9] = {0};
int applyfind(int i)
{
    while (p[i] != 0) {
        i = p[i];
    }
    return i;
}
int applyunion(int i, int j)
{
    if (i != j) {
        p[j] = i;
        return 1;
    }
    return 0;
}
int main()
{
    n = 3;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (cost[i][j] == 0) {
                cost[i][j] = inf;
            }
        }
    }
    cout << "Minimum Cost Spanning Tree:\n";
    while (ne < n) {
        int min_val = inf;
        for (int i = 0; i < n; i++) {
            for (int j = 0;
                    j < n; j++) {
                if (cost[i][j] < min_val) {
                    min_val = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = applyfind(u);
        v = applyfind(v);
        if (applyunion(u, v) != 0) {
            cout << a << " -> " << b << "\n";
            mincost += min_val;
        }
        cost[a][b] = cost[b][a] = 999;
        ne++;
    }
    cout << "Minimum cost = " << mincost << endl;
    return 0;
}

輸出

Minimum Cost Spanning Tree:
0 -> 1
1 -> 2
Minimum cost = 25

import java.util.*;
public class Main {
   static int k, a, b, u, v, n, ne = 1, min, mincost = 0;
   static int cost[][] = {{0, 10, 20},{12, 0, 15},{16, 18, 0}};
   static int p[] = new int[9];
   static int inf = 999999;
   static int applyfind(int i) {
      while(p[i] != 0)
      i=p[i];
      return i;
   }
   static int applyunion(int i,int j) {
      if(i!=j) {
         p[j]=i;
         return 1;
      }
      return 0;
   }
   public static void main(String args[]) {
      int i, j;
      n = 3;
      for(i=0; i<n; i++)
      for(j=0; j<n; j++) {
         if(cost[i][j]==0)
         cost[i][j]= inf;
      }
      System.out.println("Minimum Cost Spanning Tree: ");
      while(ne < n) {
         min = inf;
         for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
               if(cost[i][j] < min) {
                  min=cost[i][j];
                  a=u=i;
                  b=v=j;
               }
            }
         }
         u=applyfind(u);
         v=applyfind(v);
         if(applyunion(u,v) != 0) {
            System.out.println(a + " -> " + b);
            mincost += min;
         }
         cost[a][b]=cost[b][a]=999;
         ne +=1;
      }
      System.out.println("Minimum cost = " + mincost);
   }
}

輸出

Minimum Cost Spanning Tree: 
0 -> 1
1 -> 2
Minimum cost = 25

inf = 999999
k, a, b, u, v, n, ne = 0, 0, 0, 0, 0, 0, 1
mincost = 0
cost = [[0, 10, 20], [12, 0, 15], [16, 18, 0]]
p = [0] * 9
def applyfind(i):
    while p[i] != 0:
        i = p[i]
    return i
def applyunion(i, j):
    if i != j:
        p[j] = i
        return 1
    return 0
n = 3
for i in range(n):
    for j in range(n):
        if cost[i][j] == 0:
            cost[i][j] = inf
print("Minimum Cost Spanning Tree:")
while ne < n:
    min_val = inf
    for i in range(n):
        for j in range(n):
            if cost[i][j] < min_val:
                min_val = cost[i][j]
                a = u = i
                b = v = j
    u = applyfind(u)
    v = applyfind(v)
    if applyunion(u, v) != 0:
        print(f"{a} -> {b}")
        mincost += min_val
    cost[a][b] = cost[b][a] = 999
    ne += 1
print(f"Minimum cost = {mincost}")

輸出

Minimum Cost Spanning Tree: 
0 -> 1
1 -> 2
Minimum cost = 25
列印頁面
上一頁
下一頁
廣告