并查集实现kruscal 算法

一 最小生成树的条件

树上边：在最小生成树上的边

非树上边：不在最小生成树上的边

树上路径：最小生成树上两点间的唯一路径

路径最优：任一非树上边的权重都大于它所对应的树上路径上的每条边的权重。
（否则用该边形成的生成树权重更小）

割边：任意树上边把树分为两部分，连接该两部分的边为割边

割最优：任一树上边的权重都小于它所对应的割集中每条边的权重。
（否则用比该边小的割边来连接成的生成树更小）

二 kruscal 算法思想
KRUSCAL：根据路径最优构造。

算法1：（直观）
先随便构造一个树，依次检查非树上边，
如果发现破坏路径最优条件，即用该边替换一个比他大的树上边。

这个算法，可以描述，但是写出来很慢。要改进

算法2：（换个角度，即KRUSCAL）
把所有边从小到大排序，依次加入边集。
如果某边加入后成环了（非树），则PASS掉。

这样在加边的时候，因为从小到大，自然保证了路径最优。

源代码:

#include
struct edge
{
    int w;
    int x,y;
};
edge e[100];
int father[100];
int sum=0;
int cmp(const void * a, const void * b)
{
    return (*(edge*)a).w - (*(edge*)b).w;
}
void make_set(int x)
{
        parent[x] = x ;
}

int find_set(int x)        //路径压缩查找集合代表元素,可以减少合并时查找的次数
{
    if(father[x]==-1)
        return -1;
    return father[x] == find_set(father[x]);
}
int union_set(int x,int y, int w)
{
    x = find_set(x);    //x所在集合的代表
    y = find_set(y);    //y所在集合的代表
    if(x==y)        //边的两顶点原本就在同一集合,若加入这条边则会成环，所在直接返回
        return 0;
    father[x] = y;        //这是合并的关键一步,优化时可以用按秩合并,可以减小并查深度,但这样简单些
    sum+=w;
    return 1;
}
int kruscal(int n)        //n为边的数目，而不是顶点的数目
{
    //将边按权排序
    qsort(e,n,sizeof(edge),cmp);
    for(int i=0;i        union_set(e[i].x,e[i].y, e[i].w);
}