最小生成树 - Kruskal 算法 - C语言实现

基本思路：
先选择最小的边，每次选择后判断有没有回路。

struct edge{	
	int u;
    int v;
    int w;
};//存储边的关系

void Kruskal(){
    for(int i=1;i<=m;i++){
    	//判断一条边的两个顶点是否已经连通，即判断是否已在同一个集合中
        if(disjointSetMerge(e[i].u,e[i].v)) //如果目前尚未连通，则选用这条边
        {
            count++;
            sum += e[i].w
        }
        if(count == n-1) break; //直到选用了n-1条边之后退出循环
    }
    printf("%d",sum); //打印结果
}

部分函数参考点击

算法复杂度：
快速排序：$O(MlogM)$O(MlogM)
m条边找到n-1条边：$O(MlogN)$O(MlogN)
M>>N;
∴ $O(MlogM)$O(MlogM)