克鲁斯卡尔算法(Kruskal算法)求最小生成树

克鲁斯卡尔算法(Kruskal算法)求最小生成树

克鲁斯卡尔算法简介

克鲁斯卡尔算法是一种用来寻找最小生成树的算法（用来求加权连通图的最小生成树的算法）。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。

而具体的操作过程为：

a) 将图的所有连接线去掉，只剩顶点

b) 从图的边集数组中找到权值最小的边，将边的两个顶点连接起来

c)  继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边

d) 直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。

两个核心问题

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

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

 

问题一直接采用排序算法进行排序即可。

问题二的核心思想是记录处理，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

例如，使用克鲁斯卡尔算法找图 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 int
typedef struct edge{
    VertexType initial;
    VertexType end;
    VertexType 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("输入连通网的边数：
");
    scanf("%d %d",&(*vexnum),&(*arcnum));
    printf("输入连通网的顶点：
");
    for (int i=0; i<(*vexnum); i++) {
        scanf("%d",&(assists[i].value));
        assists[i].sign=i;
    }
    printf("输入各边的起始点和终点及权重：
");
    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=0; i<vexnum; i++) {
        if (assists[i].value==point) {
            return i;
        }
    }
    return -1;
}
int main(){
   
    int arcnum,vexnum;
    edge edges;
    CreateUDN(&edges,&vexnum,&arcnum);
    //对连通网中的所有边进行升序排序，结果仍保存在edges数组中
    qsort(edges, arcnum, sizeof(edges[0]), cmp);
    //创建一个空的结构体数组，用于存放最小生成树
    edge minTree;
    //设置一个用于记录最小生成树中边的数量的常量
    int num=0;
    //遍历所有的边
    for (int i=0; i<arcnum; i++) {
        //找到边的起始顶点和结束顶点在数组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];
            //计数+1
            num++;
            //将新加入生成树的顶点标记全不更改为一样的
            for (int k=0; k<vexnum; k++) {
                if (assists[k].sign==assists[end].sign) {
                    assists[k].sign=assists[initial].sign;
                }
            }
            //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
            if (num==vexnum-1) {
                break;
            }
        }
    }
    //输出语句
    for (int i=0; i<vexnum-1; i++) {
        printf("%d,%d
",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