概述

克鲁斯卡尔$(Kruskal)$算法是求连通网的最小生成树的另一种方法。与普里姆$(Prim)$算法不同，它的时间复杂度为$O(eloge)$(e为网中的边数)，所以，适合于求边稀疏的网的最小生成树 。

$Prim$和$Kruskal$，前者更适合顶点较多的时候使用；后者更适合边较少的时候使用；

算法分析

按权值由小到大的顺序排列的编辑是：（各边由起点序号，终点序号，权值表示）

1. (4,6,30)
2. (2,5,40)
3. (4,7,42)
4. (3,7,45)
5. (1,2,50)
6. (4,5,50)
7. (3,4,52)
8. (1,3,60)
9. (2,4,65)
10. (5, 6, 70)

$Kruskal$算法思想简单，但是在实现的时候需要考虑防止闭合回路的出现。

我们把属于一条边的两个顶点作为一个集合，通过这样方法就可以防止闭合回路的出现。

如果是同一条边就把两个顶点赋值相同的数值。

使用这样的结构体把数据存储起来$Edge$

typedef struct{ 
	int vex1;  //边的起始顶点 
	int vex2;  //边的终止顶点 
	int weight; //边的权值 
}Edge;

收集好图的数据以后，使用递归排序使边以从小到大(权值的的大小)的顺序排好。

这是一个递归排序 $\downarrow$

int fun(Edge arr[],int low,int high)
 {
 	int key;
 	Edge lowx;
 	lowx=arr[low];
 	key=arr[low].weight;
 	while(low<high)
 	{
 		while(low<high && arr[high].weight>=key)
 			high--;
 		if(low<high)
 			arr[low++]=arr[high];

 		while(low<high && arr[low].weight<=key)
 			low++;
 		if(low<high)
 			arr[high--]=arr[low];
	 }
	 arr[low]=lowx;
	 return low;
  } 
void quick_sort(Edge arr[],int start,int end)
{
	int pos;
	if(start<end)
	{
	pos=fun(arr,start,end);
	quick_sort(arr,start,pos-1);
	quick_sort(arr,pos+1,end);
	}
}

调用$Kruskal$算法生成最小树

void kruskal(Edge E[],int n,int e)
{ 
	int i,j,m1,m2,sn1,sn2,k,sum=0;
	int vset[n+1];
	for(i=1;i<=n;i++) //初始化辅助数组 
		vset[i]=i;
	k=1;//表示当前构造最小生成树的第k条边，初值为1 
  	j=0;//E(边集)中边的下标，初值为0
   while(k<e)//生成的边数小于e时继续循环 
   {
       m1=E[j].vex1;
       m2=E[j].vex2;//取一条边的两个邻接点 
       sn1=vset[m1];
       sn2=vset[m2];                           
	       //分别得到两个顶点所属的集合编号 
	    if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边  
	    {//防止出现闭合回路 
			printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
			sum+=E[j].weight;
			k++;   //生成边数增加 
			if(k>=n)
				break;
			for(i=1;i<=n;i++)    //两个集合统一编号
				if (vset[i]==sn2)  //集合编号为sn2的改为sn1
					vset[i]=sn1;
	    }
     j++;//扫描下一条边 
   }
    printf("最小权值之和=%d\n",sum);
}

这个算法中，这部分做的是初始化工作。

	int i,j,m1,m2,sn1,sn2,k,sum=0;
	int vset[n+1];
	for(i=1;i<=n;i++) //初始化辅助数组 
		vset[i]=i;
	k=1;//表示当前构造最小生成树的第k条边，初值为1 
  	j=0;//E(边集)中边的下标，初值为0

$vest[]$数组用于判断两个顶点是否属于同一个集合。

以权值从小到大的顺序取出每一条边(两个顶点和权值)，判断这个边两顶点是否属于同一个集合。如果属于，则取下一条边；否则记录这条最小边，然后统一这条边的两个顶点所属的集合。

   while(k<e)//生成的边数小于e时继续循环 
   {
       m1=E[j].vex1;
       m2=E[j].vex2;//取一条边的两个邻接点 
       sn1=vset[m1];
       sn2=vset[m2];                           
	       //分别得到两个顶点所属的集合编号 
	    if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边  
	    {//防止出现闭合回路 
			printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
			sum+=E[j].weight;
			k++;//生成边数增加 
			if(k>=n)
				break;
			for(i=1;i<=n;i++)    //两个集合统一编号
				if (vset[i]==sn2)  //集合编号为sn2的改为sn1
					vset[i]=sn1;
	    }
     j++;//扫描下一条边 
   }

代码

#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct{ 
	int vex1;  //边的起始顶点 
	int vex2;  //边的终止顶点 
	int weight; //边的权值 
}Edge;
void kruskal(Edge E[],int n,int e)
{ 
	int i,j,m1,m2,sn1,sn2,k,sum=0;
	int vset[n+1];
	for(i=1;i<=n;i++) //初始化辅助数组 
		vset[i]=i;
	k=1;//表示当前构造最小生成树的第k条边，初值为1 
  	j=0;//E(边集)中边的下标，初值为0
   while(k<e)//生成的边数小于e时继续循环 
   {
       m1=E[j].vex1;
       m2=E[j].vex2;//取一条边的两个邻接点 
       sn1=vset[m1];
       sn2=vset[m2];                           
	       //分别得到两个顶点所属的集合编号 
	    if(sn1!=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边  
	    {//防止出现闭合回路 
			printf("V%d-V%d=%d\n",m1,m2,E[j].weight);
			sum+=E[j].weight;
			k++;   //生成边数增加 
			if(k>=n)
				break;
			for(i=1;i<=n;i++)    //两个集合统一编号
				if (vset[i]==sn2)  //集合编号为sn2的改为sn1
					vset[i]=sn1;
	    }
     j++;//扫描下一条边 
   }
    printf("最小权值之和=%d\n",sum);
}
int fun(Edge arr[],int low,int high)
 {
 	int key;
 	Edge lowx;
 	lowx=arr[low];
 	key=arr[low].weight;
 	while(low<high)
 	{
 		while(low<high && arr[high].weight>=key)
 			high--;
 		if(low<high)
 			arr[low++]=arr[high];

 		while(low<high && arr[low].weight<=key)
 			low++;
 		if(low<high)
 			arr[high--]=arr[low];
	 }
	 arr[low]=lowx;
	 return low;
  } 
void quick_sort(Edge arr[],int start,int end)
{
	int pos;
	if(start<end)
	{
	pos=fun(arr,start,end);
	quick_sort(arr,start,pos-1);
	quick_sort(arr,pos+1,end);
	}
}
int main()
{
	Edge E[MAXE];
	int nume,numn;
	printf("输入顶数和边数:\n");
	scanf("%d%d",&numn,&nume);
	for(int i=0;i<nume;i++)
		scanf("%d%d%d",&E[i].vex1,&E[i].vex2,&E[i].weight);
	quick_sort(E,0,nume-1);
	kruskal(E,numn,nume);
}
//INPUT要输入的：
//6 10
//1 2 6
//1 3 1
//1 4 5
//2 3 5
//2 5 3
//3 4 5
//3 5 6
//3 6 4
//4 6 2
//5 6 6

实验名称

最小生成树算法-Kruskal算法

实验目的

1.掌握并查集的合并优化和查询优化； 2.掌握Kruskal算法。 3.能够针对实际问题，能够正确选择贪心策略。 4.能够针对选择的贪心策略，证明算法的正确性。 5.能够根据贪心策略，正确编码。 6.能够正确分析算法的时间复杂度和空间复杂度

实验内容

采用Kruskal算法生成最小生成树，并采用并查集的合并优化和查询优化。

实验环境

操作系统：win 10; 编程语言：Java，JDK1.8； 开发工具：IDEA；

实验过程

算法简介

Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

算法步骤

Kruskal算法又称加边算法，初始最小生成树的边数是0，每次迭代都从边的集合中选取最小代价的边，我们称他为最小代价边，加入到最小生成树的边集合中。

将图中所有的边按照权值大小从小到大排序。
把N个顶点看成独立的森林。
从排好序的边集合中取出当前最小的边，所选连接的顶点是v,w，如果两个顶点添加到最小生成树中后不会构成环，那就加入，反之跳过本次循环。
重复步骤三，直到所有顶点添加完成或者最小生成树的边的数量=顶点数-1。

代码实现

代码总体分为三部分，分别是最小生成树的生成，并查集的构建，对边权值的处理。 并查集用来快速判断两个元素加入到生成树中会不会构成环，如果两个元素加入到并查集中是属于同一个分组，代表构成环，所以直接continue;反之，将这条边加到独立的最小生成树中，边数++，并更新总权值，如果边数==顶点数-1；退出循环。权值处理主要是通过排序将边的权值按照从小到大的顺序添加到最小生成树中，排序可以选择内置的快排或者堆排。

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Kruskal {

    /**
     * 最小生成树的权值之和
     */
    private int mstCost;

    //获取最小生成树的总权值
    public int getMstCost() {
        return mstCost;
    }

    /**
     * 最小生成树的边的列表
     */
    private List<int[]> mst;

    //获取最小生成树的边的集合
    public List<int[]> getMst() {
        return mst;
    }

    /**
     * @param V     总结点数
     * @param edges 每条边的定义：[起始点, 终点, 权值]
     */
    public Kruskal(int V, int[][] edges) {
        //E代表一共多少条边
        int E = edges.length;
        //边数小于顶点数是构不成最小生成树
        if (E < V - 1) {
            throw new IllegalArgumentException("参数错误");
        }
        mst = new ArrayList<>(E - 1);

        // 体现了贪心的思想，从权值最小的边开始考虑 这里采用了排序的思想，来获取最小边
        Arrays.sort(edges, Comparator.comparingInt(o -> o[2]));
        //创建一个并查集
        UnionFind unionFind = new UnionFind(V);
        // 当前找到了多少条边
        int count = 0;
        for (int[] edge : edges) {
            // 如果形成了环，就继续考虑下一条边
            if (unionFind.isConnected(edge[0], edge[1])) {
                continue;
            }
            //如果没有形成环，将两个顶点连接在一个集合
            unionFind.union(edge[0], edge[1]);
            //加上这条边的权值
            this.mstCost += edge[2];
            //最小生成树加上这条边
            mst.add(new int[]{edge[0], edge[1], edge[2]});
            //当前最小生成树的边数++
            count++;
            //循环结束条件，v个顶点有v-1条边构成最小生成树
            if (count == V - 1) {
                break;
            }
        }
    }

    /**
     * 并查集
     */
    private class UnionFind {
        //每个并查集中的节点都有一个“大哥”
        private int[] parent;
        //并查集中的分组数
        private int count;
        //N代表并查集中节点的总数
        private int N;

        public UnionFind(int N) {
            this.N = N;
            this.count = N;
            this.parent = new int[N];
            for (int i = 0; i < N; i++) {
                //各个节点的初始父节点都是他们自己
                parent[i] = i;
            }
        }

        /**
         * 查找指定元素在哪一个分组，也就是节点跟随最终的“大哥”是谁
         *
         * @param x
         * @return
         */
        public int find(int x) {
            while (x != parent[x]) {
                x = parent[x];
            }
            return x;
        }

        /**
         * 合并两个元素所在的分组，将两个顶点的大哥统一
         *
         * @param x
         * @param y
         */
        public void union(int x, int y) {
            //找到他们各自的祖节点，
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                return;
            }
            //合并之后分组总数--
            parent[rootX] = rootY;
            count--;
        }

        public int getCount() {
            return count;
        }

        //判断是不是同一个分组，也就是两个元素是不是同一个大哥的小弟
        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }

    public static void main(String[] args) {
        int N = 7;
        //edges[0] 表示起始顶点，edges[1]表示终止定点，edges[2]代表这条边的权值
        int[][] edges = {{0, 1, 4},
                {0, 5, 8},
                {1, 2, 8},
                {1, 5, 11},
                {2, 3, 3},
                {2, 6, 2},
                {3, 4, 3},
                {4, 5, 8},
                {4, 6, 6},
                {5, 6, 7},
        };
        //顶点是0-6，一共10条边
        Kruskal kruskal = new Kruskal(N, edges);
        //总权值
        int mstCost = kruskal.getMstCost();
        System.out.println("最小生成树的权值之和：" + mstCost);
        List<int[]> mst = kruskal.getMst();
        System.out.println("最小生成树的边的列表：");
        for (int[] edge : mst) {
            System.out.println("[起始顶点：" + edge[0] + "-终止顶点" + edge[1] + "]" + "，权值：" + edge[2]);
        }
    }
}

复杂度分析

并查集查找空间复杂度是O(n)，合并和判断是不是同一个集合时间复杂度是O(1)； Kruskal算法的时间复杂度：O(E log E)，这里 E 是图的边数； 空间复杂度：O(V)，这里 V 是图的顶点数，并查集需要 V 长度的数组空间。

Kruskal算法简介：

Kruskal 算法是一种用来求最小生成树的算法，在稀疏图中比 Prim 有更高的效率，且方便实现，所以本文重点讲解 Kruskal 算法的用途和使用方法

Kruskal算法原理：

Kruskal 算法主要利用贪心的思想使得边权和最小

Kruskal 算法步骤：

1. 把 $m$ 条边按边权从小到大排序
2. 把图中的 $n$ 个顶点看成独立的 $n$ 棵树组成的森林；
3. 先从边权小的边开始循环，通过并查集判断添加这条边后是否会形成环（也就是能否连接两个不同祖先的点），如果可以，则添加这条边。
4. 重复第三点，直到添加了 $n-1$ 条边后停止循环

Kruskal算法实现：

我们以 【模板】最小生成树 作为例题进行分析

题目分析：

该题是一个很典型的最小生成树例题，并且适合用Kruskal算法解决，代码如下：

//最小生成树模板
#include<bits/stdc++.h>
using namespace std;

struct Edge {
	int u;//表示边的起点
	int v;//表示边的终点
	int w;//表示边权
} edge[200001];

bool cmp(Edge a,Edge b) {
	return a.w<b.w;  //快速排序条件
}

int f[5001]; //用来存每个点的祖先
int zhao(int x) {  //用来找点的祖先
	if(f[x]!=x) return f[x]=zhao(f[x]); //如果x的祖先就是x，则返回x,否则递归查询x祖先的祖先
	else return x;
}

int n,m,i,j,sum,cnt;  //n是点数，m是边数，i,j为循环变量，sum用来计算边权和，cnt用来计算当前选定边数
int kruskal() {  // kruskal算法核心
	sort(edge+1,edge+m+1,cmp);  //先将边按边权从小到大排序
	for(i=1; i<=m; ++i) {   //循环查询边
		if(zhao(edge[i].u)==zhao(edge[i].v)) continue;  //如果选择该边会形成环（也就是无法连接两个不同祖先的点），则跳过该边
		sum+=edge[i].w; //如果执行到这一步，就代表该边满足条件，则累加边权
		f[zhao(edge[i].u)]=zhao(edge[i].v);  //将两点合并
		if(++cnt==n-1) break;  //如果已经添加了n-1 条边，则跳出循环
	}
}

int main() {
	cin>>n>>m;
	for(i=1; i<=m; ++i) {
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //输入数据
	}
	for(i=1; i<=n; ++i) f[i]=i; //并查集初始化
	kruskal(); //kruskal算法计算
	if(cnt==n-1) { //如果已经添加了n-1 条边（也就是已经形成了连通图），输出边权
		cout<<sum;
		return 0;
	}
	puts("orz"); //如果没有形成连通图，输出orz
}

还有有疑问可以在此处寻找更多优秀文章或者在评论中提出哦~

图片来源：勿在浮沙筑高台

如果有帮助的话点个赞再走呗~