克鲁斯卡尔最小生成树算法
克鲁斯卡尔最小生成树算法是查找图的最小生成树的有效方法之一。最小生成树是连接主图中所有顶点的子图，该子图的边数尽可能少，且成本（分配给每条边的权重之和）最小。
该算法首先从图的森林（定义为仅包含主图顶点的子图）开始，然后添加成本最小的边，直到创建最小生成树且图中不形成环路。
克鲁斯卡尔算法比普里姆算法更容易实现，但复杂度更高。
克鲁斯卡尔算法
克鲁斯卡尔算法的输入是图 G {V, E}，其中 V 是顶点集合，E 是边集合，输出是源顶点 S 和图 G 的最小生成树。
算法
将图中的所有边按升序排列，并将其存储在数组 edge[] 中。
在一个包含所有顶点的平面上构建图的森林。
从 edge[] 数组中选择成本最小的边，并将其添加到图的森林中。将已访问的顶点添加到 visitor[] 数组中，以标记它们。
重复步骤 2 和 3，直到所有顶点都被访问，并且图中没有形成任何循环。
当所有顶点都被访问后，最小生成树就形成了。
计算形成的输出生成树的最小成本。
示例
使用克鲁斯卡尔算法为下图构建最小生成树 −
解决方案
第一步，按升序对给定图中的所有边进行排序，并将值存储在数组中。
| Edge | B→D | A→B | C→F | F→E | B→C | G→F | A→G | C→D | D→E | C→G |
|---|---|---|---|---|---|---|---|---|---|---|
| Cost | 5 | 6 | 9 | 10 | 11 | 12 | 15 | 17 | 22 | 25 |
然后，在单个平面上构建给定图的森林。
从已排序的边成本列表中，选择成本最小的边并将其添加到输出图中的森林中。
B → D = 5
最小成本 = 5
访问数组，v = {B, D}
类似地，下一个成本最小的边是 B → A = 6；所以我们把它添加到输出图中。
最小成本 = 5 + 6 = 11
访问数组，v = {B, D, A}
下一个成本最低的边是 C → F = 9;将其添加到输出图中。
最小成本 = 5 + 6 + 9 = 20
访问数组，v = {B, D, A, C, F}
下一个要添加到输出图中的边是 F → E = 10.
最小成本 = 5 + 6 + 9 + 10 = 30
已访问数组，v = {B, D, A, C, F, E}
最小成本数组中的下一条边是 B → C = 11，因此我们将其添加到输出图中。
最小成本 = 5 + 6 + 9 + 10 + 11 = 41
访问数组，v = {B, D, A, C, F, E}
最小成本数组中最后一条要添加到输出图中的边是 F → G = 12。
最小成本 = 5 + 6 + 9 + 10 + 11 + 12 = 53
已访问数组，v = {B, D, A, C, F, E, G}
得到的结果是给定图的最小生成树，成本 = 53。
示例
最终程序实现了克鲁斯卡尔最小生成树问题，该问题以成本邻接矩阵作为输入，并打印最短路径和最小成本作为输出。
#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:
");
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
", 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:
";
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 << "
";
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
