kruskal算法是什么？

kruskal算法是求加权连通图的最小生成树的算法。

kruskal算法总共选择n- 1条边，(共n个点)所使用的贪心准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。

kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

Kruskal算法基本思想：

每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量。

排序使用Quicksort(O(eloge))。

检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数。

Union-Find使用rank启发式合并和路径压缩。

总复杂度O(eloge)=O(elogv) (因为e<n(n-1)/2)。

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；

对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。

图 1 连通网

请点击输入图片描述

例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：

首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：

（1）

请点击输入图片描述

对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如（2）所示：

（2）

请点击输入图片描述

其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

（3）

请点击输入图片描述

其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

（4）

请点击输入图片描述

然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：

（5）

请点击输入图片描述

继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：

（6）

请点击输入图片描述

当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。

实现代码：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initialVertexType endVertexType weight}edge[MAX_VERtEX_NUM]//定义辅助数组typedef struct {VertexType value//顶点数据int sign//每个顶点所属的集合}assist[MAX_VERtEX_NUM]assist assists//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序int cmp(const void *a,const void*b){return  ((struct edge*)a)->weight-((struct edge*)b)->weight}//初始化连通网void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("输入连通网的边数：\n")scanf("%d %d",&(*vexnum),&(*arcnum))printf("输入连通网的顶点：\n")for (int i=0i<(*vexnum)i++) {scanf("%d",&(assists[i].value))assists[i].sign=i}printf("输入各边的起始点和终点及权重：\n")for (int i=0 i<(*arcnum)i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight)}}//在assists数组中找到顶点point对应的位置下标int Locatevex(int vexnum,int point){for (int i=0i<vexnumi++) {if (assists[i].value==point) {return i}}return -1}int main(){int arcnum,vexnumedge edgesCreateUDN(&edges,&vexnum,&arcnum)//对连通网中的所有边进行升序排序，结果仍保存在edges数组中qsort(edges, arcnum, sizeof(edges[0]), cmp)//创建一个空的结构体数组，用于存放最小生成树edge minTree//设置一个用于记录最小生成树中边的数量的常量int num=0//遍历所有的边for (int i=0i<arcnumi++) {//找到边的起始顶点和结束顶点在数组assists中的位置int initial=Locatevex(vexnum, edges[i].initial)int end=Locatevex(vexnum, edges[i].end)//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路if (initial!=-1&&end!=-1&&assists[initial].sign!=assists[end].sign) {//记录该边，作为最小生成树的组成部分minTree[num]=edges[i]//计数+1num++//将新加入生成树的顶点标记全不更改为一样的for (int k=0k<vexnumk++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign}}//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环if (num==vexnum-1) {break}}}//输出语句for (int i=0i<vexnum-1i++) {printf("%d,%d\n",minTree[i].initial,minTree[i].end)}return 0}

测试数据：

输入连通网的边数：

6 10

输入连通网的顶点：

1

2

3

4

5

6

输入各边的起始点和终点及权重：

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

1,3

4,6

2,5

3,6

2,3

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。

例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。

克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。

基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。

具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。

以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。

第1步 ：将边<E,F>加入R中。

边<E,F>的权值最小，因此将它加入到最小生成树结果R中。

第2步 ：将边<C,D>加入R中。

上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。

第3步 ：将边<D,E>加入R中。

上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。

第4步 ：将边<B,F>加入R中。

上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。

第5步 ：将边<E,G>加入R中。

上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。

第6步 ：将边<A,B>加入R中。

上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时，最小生成树构造完成！它包括的边依次是： <E,F><C,D><D,E><B,F><E,G><A,B> 。

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：

问题一 对图的所有边按照权值大小进行排序。

问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一用排序算法排序即可。

问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：

在将<E,F><C,D><D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然<C,E>是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想

对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！

第1步 ：将顶点A加入到U中。

此时，U={A}。

第2步 ：将顶点B加入到U中。

上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。

第3步 ：将顶点F加入到U中。

上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。

第4步 ：将顶点E加入到U中。

上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。

第5步 ：将顶点D加入到U中。

上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。

第6步 ：将顶点C加入到U中。

上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。

第7步 ：将顶点G加入到U中。

上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

---