算法学习之路|最小生成树—kruskal

算法概述:一个带权的连通图， 有V个点，E个边，去掉所有的边，得到一个新图，将E个边按权值从小到大排列，然后从权值最小的边<u,v>开始加入,重复下去，但每次加入之前要判断u，v是否连通，若连通则不加入，直到全部连通为止，结束循坏。

代码：

struct Edge
{
    int u;//边起点
    int v;//边终点
    int w;//权值
}E[N];
int V;//点数
int E;//边数
bool cmp(const Edge *a ,const Edge *b)  
{  
    return *(Edge *)a.w - *(Edge *)b.w ;          //从小到大排序，把a，b位置反过来就是从大到小   
} 
void kruskal()
{
    int i,j,p,q,k;
    int _set[N];
    sort(E,E+N);
    for(i=0;i<E;i++)
    {
        _set[i]=i;
    }
    k=1;
    j=0;
    while (k<E)  
    {   
        p=_set[E[j].u];  
        q=_set[E[j].v];                                     
        if (p!=q)                         
        {
            k++;  
            for (i=0;i<E;i++)  
            {  
                if (_set[i]==q)  
                {  
                    vset[i]=p;  
                }  
            }             
        }  
        j++;  
    }  

}