克鲁斯卡尔算法(Kruskal)

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止 [2] 。

和普利姆算法以顶点去构建最小生成树不同的是，克鲁斯卡尔算法以边来构建最小生成树。克鲁斯卡尔算法的时间复杂度为O(eloge)。它针对与稀疏图的效率较高。注意：初始化条件一定包含的是对边集的排序算法。

最核心的其实就是这个简单的Find算法，要理解并且记住它。

#include "邻接矩阵"
typedef struct {
    int begin;
    int weight;
    int end;
} Edge;/*Kruskal算法所需要用到的边集*/
void Kruskal(MGraph G){
    int i, n, m;
    Edge edges[MAXEDGE];
    int parent[MAXVEX];
    /*此处省略了将一个邻接矩阵转换为对应的边集表的代码，这部分代码很简单*/
    /*同时也省略了对于边集edges的排序算法：edges[i]是从i = 0 到 i = G.numEdges 从小到大递增的*/
    for(i = 0; i < G.numVexes; i++){
        n = Find(parent, edges[i].begin);
        /*分别找到 第i条边的起始点顶和尾顶点的下一个结点(这个信息存放在parent数组)*/
        /*对于i=0的时候，parent数组全为0，所以返回的时候n是肯定不等于m的*/
        m = Find(parent, edges[i].end);
        /*这两个值如果不相等意味着没有形成环，反之则是形成了环*/
        if(n != m){
            parent[n] = m; 
            /*表明n到m之间是有路的。对parent的理解非常重要！
            这里有篇博客讲的不错：https://blog.csdn.net/qq_31709249/article/details/100855661?utm_medium=distribute.pc_relevant.none-              task-blog-BlogCommendFromBaidu-6.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-                                BlogCommendFromBaidu-6.channel_param
            */
            printf("(V%d V%d) %d", edges[i].begin, edges[i].end, edges[i].weight);
            /*打印边信息*/
        }
    }
}
int Find(int * parent, int f){
    while(parent[f] > 0){
        f = parent[f];
    }
    return f;
}

对于Parent数组的理解(不对请指出啦！！)

n == m 的情况:

image

n != m 的情况:

image