kruskal算法(读者可以将其称为“巡航卷曲算法”)也是解决最小生成树问题的算法。 与prim算法不同，kruskal算法采用边贪心的策略，其思想极其简洁，理解难度比prim算法低得多。
kruskal算法的基本思想是：
默认情况下，图表中的所有边都将隐藏，图表中的每个顶点都将成为一个连接块。 然后，执行以下步骤：
所有边按边权从小到大的顺序排列。
按照边缘权从小到大的顺序测试所有边缘，如果当前测试边连接的两个顶点不在同一连接块上，则将该测试边添加到当前最小生成树中； 否则，边缘将被放弃。
)执行步骤，直到最小生成树中的边数从总顶点数中减去1或测试完所有边为止。 另外，如果完成时最小生成树的边数小于总顶点数减去1，则此图不相连。
简单来说，kruskal算法的思路是每次选择图中最小边权的边，如果边两端的顶点位于不同的连接块，则将该边添加到最小生成树中。 解决代码实现的问题吧。 首先是边缘的定义。 kruskal算法需要判断边的两个端点是否在不同的连接块上，因此边的两个端点的编号是必须的，算法涉及边权，因此也需要边权。 因此可以定义结构体，硬声收纳边缘的两个端点号和边缘权可以满足需要。
结构边缘{ int u，v； //边两端的编号int cost； //边疆权}E[MAXV]； //最多有MAXV条边，解决了边的定义后，您需要编写一个排序函数，按边权重从小到大对数组e进行排序，请尝试自定义sort的cmp函数：
OOLCMP(edgea，edge b ) {return a.cost b.cost； }接下来，为了解决kruskal算法本身的实现，让我们来看看伪代码。 请注意结合前面说明的基本思想进行理解。
int kruskal ()将最小生成树的边缘权之和设置为ans，最小生成树的当前边缘数Num_Edge； 所有边缘按边缘权从小到大排序； for (从小到大排列所有边缘(if )将当前测试边缘的两个端点位于不同的连接块中)测试边缘添加到最小生成树； ans =测试边缘边缘权的最小生成树的当前边缘数Num_Edge； 边缘数Num_Edge从顶点数中暂时减去而结束循环时； } }返回Ans； }这个伪代码有两个看起来不直观的细节。 也就是说
如何判断测试边缘的两端是否位于不同的连接块上。
如何将测试边添加到最小生成树中。
其实，对于这两个问题，可以改变看法。 将各连接块视为一个集合，可以转化为判断两个端点是否在同一集合的问题，该问题如前所讨论的，为并査集。 并集可以通过调查两个节点所在集合的根节点是否相同来判断是否在同一集合中，而并集功能正好可以解决上述第二个细节。 也就是说，如果将具有测试边缘两个端点的集合结合起来，就可以得到将边缘添加到最小生成树中的效果。
因此，基于以上解释，可以编写kruskal算法的代码。 另外，由于假设主题中的顶点编号的范围为[1，n]，所以在初始化并行检查集时不能弄错范围。 如果下标从0开始，则在整个代码中也只需修改初始化的部分进行检查即可。
int father[N]； //排序数组intfindfather(intx )//排序查询函数……) } //kruskal函数返回最小生成树的边缘权重之和，参数n是顶点数，m是图表的边缘数intkruskal i=n； I ) ) /主题顶点范围为[1，n] father[i]=i； //排列检查组初始化}sort(e、E m、cmp )； //所有边按边权从小到大的顺序为for(intI=0； im； I ) ) /列出所有边intfau=findfather(e[I].u )； //具有查询测试边的集合根节点intfav=findfather(e[I].v )； if(Fau！=fav(//如果不在一个集合father[faU]=faV； //合并集合(即，将测试边添加到最小生成树) ans =E[i].cost； //增加边权之和测试边权Num_Edge生成树的边缘数1if(num_edge==n-1 )//边缘数等于顶点数到暂时终止算法break； }if(num_edge！=n-1 )返回- 1； //无法接通，返回-1e
lsereturn ans;//返回最小生成树的边权之和 }可以看到，kruskal算法的时间复杂度主要来源于对边进行排序，因此其时间复杂度O(ElogE)，其中E为图的边数。显然 kruskal适合顶点数较多、边数较少的情况，这和prim算法恰好相反。于是可以根据题目所给的数据范围来选择合适的算法，即如果是稠密图(边多)，则用prim算法；如果是稀疏图(边少)，则用kruskal算法。
另外，一定会有读者疑惑，使用 kruskal算法能否保证最后一定能形成一棵连通的树？这个问题的前提是必须在连通图下讨论，如果图本身不连通，那么一定无法形成一棵完整的最小生成树。而对问题本身的讨论则需要分3个部分：
①由于图本身连通，因此每个顶点都会有边连接。而一开始每个结点都视为一个连通块，因此在枚举过程中一定可以把每个顶点都访问到，且只要是第一次访问某个顶点，对应的边一定会被加入最小生成树中，故图中的所有顶点最后都会被加入最小生成树中。
②由于只有当测试边连接的两个顶点在不同的连通块中时才将其加入最小生成树，因此定不会产生环。而如果有两个连通块未被连接，要么它们本身就无法被连接（也就是非连通图），要么它们之间一定有边。由于所有边都会被测试，因此两个连通块最终一定会被连接在一起。故最后一定会生成一个连通的结构。
③由于算法要求当最小生成树中的边数等于总顶点数减1时结束，因此由连通、边数等于顶点数减1这两点可以确定，最后一定能生成一棵树。
上图求解最小生成树：
程序代码：
#include<cstdio>#include<algorithm>using namespace std;const int MAXV = 1000;//最大顶点数const int INF = 1000000000;//设INF为一个很大的数 //边集定义部分 struct edge {int u,v;//边的两个端点编号int cost;//边权 }E[MAXV]; //最多有MAXV条边 bool cmp(edge a,edge b){return a.cost < b.cost;} //并查集部分 int father[MAXV];//并查集数组int findFather(int x){//并查集查询函数 int a=x;while(x != father[x]){x = father[x];}//路径压缩while(a != father[a]){int z = a;a = father[a];father[x] = x; } return x;} //kruskal函数返回最小生成树的边权之和，参数n为顶点个数，m为图的边数int kruskal(int n,int m){//ans为所求边权之和，Num_Edge为当前生成树的边数int ans = 0, Num_Edge = 0;for(int i=1; i<= n;i++){//假设题目中顶点范围为[1,n] father[i] = i;//并查集初始化 } sort(E,E+m,cmp);//所有边按边权从小到大排序for(int i=0;i<m;i++){//枚举所有边 int faU = findFather(E[i].u);//查询测试边所在的集合根结点int faV = findFather(E[i].v);if(faU != faV){//如果不在一个集合 father[faU] = faV;//合并集合（即把测试边加入最小生成树中） ans += E[i].cost;//边权之和增加测试边的边权Num_Edge++;//生成树的边数+1if(Num_Edge == n-1)//边数等于顶点数减一时结束算法 break; }} if(Num_Edge != n-1)return -1;//无法连通，返回-1elsereturn ans;//返回最小生成树的边权之和 } int main(){int n,m;scanf("%d%d",&n,&m);//顶点个数，边数，起点编号for(int i=0;i<m;i++){scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost);//两个端点编号、边权 } int ans = kruskal(n,m);// kruskal算法入口printf("%dn",ans);return 0; }输入数据：
6 100 1 40 4 10 5 21 2 11 5 32 3 62 5 53 4 53 5 44 5 3输出结果：