克鲁斯卡尔的最小生成树

Kruskal 的最小生成树算法是寻找图的最小生成树的有效方法之一。最小生成树是一个子图，它将主图中存在的所有顶点与最少可能的边和最小成本（分配给每个边的权重之和）连接起来。

该算法首先从图的森林（定义为仅包含主图的顶点的子图）开始，随后添加最小成本边，直到创建最小生成树，而不会在图中形成循环。

Kruskal算法比prim算法更容易实现，但复杂度更高。

克鲁斯卡尔算法

kruskal算法的输入是图G{V,E}，其中V是顶点集合，E是边集合，得到源顶点S和图G的最小生成树作为输出。

算法

  • 将图中所有边按升序排序，存入数组edge []中。

边缘
成本

  • 在包含所有顶点的平面上构建图的森林。

  • 从edge[]数组中选择成本最低的边并将其添加到图的森林中。通过将访问过的顶点添加到visited[]数组中来标记它们。

  • 重复步骤 2 和 3，直到访问了所有顶点且图中没有形成任何循环

  • 当所有的顶点都被访问后，最小生成树就形成了。

  • 计算形成的输出生成树的最小成本。

例子

使用克鲁斯卡尔算法为下面给出的图构建最小生成树 -

kruskals_algorithm_graph

解决方案

第一步，按升序对给定图中的所有边进行排序，并将值存储在数组中。

边缘 乙→丁 A→B 中→中 F→E 乙→丙 G→F A→G C→D D→E C→G
成本 5 6 9 10 11 12 15 17 号 22 25

然后，在单个平面上构建给定图的森林。

单平面上的图

从已排序的边成本列表中，选择成本最低的边并将其添加到输出图中的森林中。

B → D = 5
Minimum cost = 5
Visited array, v = {B, D}
排序边成本

类似地，下一个最小成本边是 B → A = 6；所以我们将它添加到输出图上。

Minimum cost = 5 + 6 = 11
Visited array, v = {B, D, A}
图b到a

下一个最小成本边是 C → F = 9；将其添加到输出图上。

Minimum Cost = 5 + 6 + 9 = 20
Visited array, v = {B, D, A, C, F}
图c到f

要添加到输出图的下一条边是 F → E = 10。

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

最小成本数组的下一条边是 B → C = 11，因此我们将其添加到输出图中。

Minimum cost = 5 + 6 + 9 + 10 + 11 = 41
Visited array, v = {B, D, A, C, F, E}
最小成本数组

要添加到输出图中的最小成本数组的最后一条边是 F → G = 12。

Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53
Visited array, v = {B, D, A, C, F, E, G}
输出图f到g

获得的结果是给定图的最小生成树，成本= 53。

例子

最终程序实现了 Kruskal 的最小生成树问题，该问题将成本邻接矩阵作为输入，并打印最短路径作为输出以及最小成本。

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:\n")
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"\n\tMinimum cost = \n{mincost}")

输出

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