1 问题描述
何为Kruskal算法？
该算法功能：求取加权连通图的最小生成树。假设加权连通图有n个顶点，那么其最小生成树有且仅有n - 1条边。
该算法核心思想：从给定加权连通图中，选择当前未被选择的，不能形成回路且权值最小的边，加入到当前正在构造的最小生成树中。
2 解决方案
2.1 构造最小生成树示例
下面请看一个具体示例：
给定一个加权连通图，其包含5个顶点，分别为：1,2,3,4,5。包含7条边，按照从小到大排序依次为：
1-2,5
2-3,5
3-5,6
2-4,12
4-5,12
2-5,15
3-4,17
那么可知，使用kruskal算法构造该加权连通图的最小生成树，则需要选择出这7条边中满足定义的4条边。
(1)原始图
(2)添加第1条边
此时未选中任何一条边，那么直接选择7条边中最小的一条边，2-3,5。（PS：当权值最小的边有多个时，只要满足定义，可以随意选择一条边即可。例如，此处也可以选择1-2,5）
(2)添加第2条边
此时，从剩余的6条边中选择最小权值的边，可以轻易知道为1-2,5。加入此边后，检查此时的正在构造的最小生成树，没有回路，符合定义，即可以确认加入。
(3)添加第3条边
此时，从剩余的5条边中选择最小权值且不会生成环的边，轻易可知，3-5,6符合要求。
(4)添加第4条边（PS：此时也是最小生成树的最后一条边）
从剩余的4条边中选择最小权值且不会生成回环的边，发现2-4,12、4-5,12均符合要求，此时，任意选择其中一条边即可。这里，我选择的是4-5,12。
(5)最小生成树以及构造完毕，结束构造。
2.2 伪码及时间效率分析
该算法在开始的时候，会将给定连通图所有边的权值进行从小到大排列。然后，从一个空子图开始，它会扫描这个这个有序列表，并试图把列表中的下一条边加入到当前正在构造的子图（或者说是最小生成树）中。当前，这种添加不能形成一个回路，如果产生了回路，则把这条边跳过。
通过以上的伪码，可以知道，Kruskal算法的时间效率取决于两点：
（1）对给定连通图所有边权值进行排序的时间效率；
（2）对新加入边，进行是否形成回路判断的时间效率。
首先，谈谈（1）的时间效率。对于排序算法，一般的时间效率分为O(n^2)（例如，选择排序和冒泡排序）和O(nlogn)（例如，合并排序和快速排序）。由于合并排序，相对于快速排序要稳定，所以，此处我们可以选择合并排序来处理问题（1），即时间效率为O(nlogn)，其中n为顶点总数。
其次，谈谈（2）的时间效率。对于问题（2）中要实现的功能，有一些高效的算法可以实现这种功能，这些算法的核心就是对两个顶点是否属于同一棵树的关键性检查，它们被称为并查算法，而该算法能够达到的最优时间效率为O(eloge)，其中e为具体边总数。
最后，我们来探讨一下使用并查算法实现（2）中要求的功能。
使用并查算法实现检查回环问题，这里涉及的是一种抽象数据类型，这种数据类型是由某个有限集的一系列不相交子集以及下面这些操作构成的。
id(x)生成一个单元集合{x}。假设这个操作对集合S的每一个元素只能应用一次。
find(x)返回一个包含x的子集。
union(x, y)构造分别包含x和y的不相交子集Sx和Sy的并集，并把它添加到子集的集合中，以代替被删除后的Sx和Sy。
例如，其中S = {1， 2， 3， 4， 5， 6}。首先使用id(x)，初始化结果：{1}，{2}，{3}，{4}，{5}，{6}。
现在执行union(1,4)得到{1,4}，执行union(4,5)得到{1,4,5}，此时集合结果：{1,4,5}，{2}，{3}，{6}。
那么此时执行find(1)或者find(4)或者find(5)返回子集{1,4,5}，执行find(3)返回子集{3}。
上面就是并查算法的应用思想，那么影响并查算法的时间效率，就是id(x)和union(x)函数的具体实现来决定。
此处对于id(x)和union(x)的实现，我采用树的性质来实现，把已经构造的边形成一棵树，当有新增的边时，且新增的边所在树的层数或者所有节点总数小于当前构造的树，那么我们就把新增的边所在树的根节点改变成当前正在构造的树的根节点的直接子节点。
例如合并子集{1,4,5,2}（PS：该子集构成的树根节点为1）}和{3,6}（PS：该子集构成的树的根节点为3），那么可以把根节点3直接转换为1的一个直接子节点即可。具体如下图所示：
讲完上面的定义及思想，下面就来具体看看对于2.1中示例图实现的编码应用。
首先，是初始化id(x)，这里我首先令每一个单节点树的id(x)值为-1。
然后，是find(x)的实现：
最后，是union(x)的实现:
到这里后，看一下，构造树型id(x)值的具体图：
首先顶点1到5的id(x) = {-1, -1, -1, -1, -1}，即表示刚开始，所有顶点均为根节点。(PS:后面示例id(x)、find(x)和union(x, y)中对于数组中元素均为1开始，不是0开始计算数组中元素，这样是方面描述，请大家不要见怪哟。注意，下面图中id = 2表示根节点为顶点3)
（1）选择第1条边，2-3，5
此时id(2) = -1，find(2) = 2根节点为2。id(3) = -1，find(3) = 3根节点为3。根据union(x)函数可知，由于id(find(2)) >= id(find(3))，所以id(find(2)) = idb = 2，id(find(3)) = num = -2
此时id(x) = {-1, 2, -2, -1, -1 }
（2）选择第2条边，1-2,5
此时，id(1) = -1，find(1) = 1根节点为1。Id(2) = 2，find(2) = 3根节点为3。根据union(x)函数可知，由于id(find(1)) > id(find(2))，所以id(find(1)) = idb = 2，id(find(2)) = num = -3
此时id(x) = {2, 2, -3, -1, -1 }
（3）选择第3条边，3-5,6
此时，id(3) = -3，find(3) = 3根节点为3。Id(5) = -1，find(5) = 5根节点为5。根据union(x)函数可知，由于id(find(3)) < id(find(5))，所以id(find(5)) = ida = 2，id(find(3)) = num = -4
此时id(x) = {2, 2, -4, -1, 2}
（4）选择第4条边，4-5,12（此处也是最小生成树的最后一条边）
此时，id(4) = -1，find(4) = 4根节点为4。Id(5) = 2，find(5) = 3根节点为3。根据union(x)函数可知，由于id(find(4)) > id(find(5))，所以id(find(4)) = idb = 2，id(find(5)) = num = -5
此时id(x) = {2, 2, -5, 2, 2 }
2.3 具体编码（最佳时间效率）
运行结果：