最小生成树Kruskal算法

Kruskal算法就是把图中的所有边权值排序，然后从最小的边权值开始查找，连接图中的点，当该边的权值较小，但是连接在途中后会形成回路时就舍弃该边，寻找下一边，以此类推，假设有n个点，则只需要查找n-1条边即可。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

const int maxn=;

int v,l;///v代表点的个数，l代表边的个数

int fa[maxn],son[maxn];

struct Kruskal{///该结构体时存储点与这两点之间的距离的

int a,b;

int value;

}edge[maxn];

bool cmp(Kruskal x,Kruskal y){///把边的权值按从小到大的顺序排列

return x.value<y.value;

}

int fin(int x)///寻找x的根结点

{

    return fa[x]==x?fa[x]:fin(fa[x]);

}

bool unin(int x,int y)

{

    int root1,root2;

    root1=fin(x);

    root2=fin(y);

    if(root1==root2){

        return false;///当输入的两个点有相同的根结点时成环，返回false

    }

    else if(son[root1]>=son[root2]){

        fa[root2]=root1;///root2的根结点时root1

        son[root1]+=son[root2];///把数量少的那棵树连接到数量多的那棵树

    }

    else {

        fa[root1]=root2;

        son[root2]+=son[root1];

    }

    return true;///只要两个点不在同一个根结点上就返回true

}

int main()

{

    int n,total,sum,flag;

    cin>>n;

    while(n--){

        cin>>v>>l;

        total=;

        sum=;

        flag=;

        for(int i=;i<=v;i++){///初始化

            fa[i]=i;

            son[i]=;

        }

        for(int i=;i<=l;i++){

            cin>>edge[i].a>>edge[i].b>>edge[i].value;

        }

        sort(edge+,edge++l,cmp);///因为edge时从1开始的，所以edge要+1

        for(int i=;i<=l;i++){

            if(unin(edge[i].a,edge[i].b)){

                total++;

                sum+=edge[i].value;///记录最小的权值

                cout<<edge[i].a<<"->"<<edge[i].b<<endl;

            }

            if(total==v-){///有n个结点就有n-1条边构成最小生成树

                flag=;

                break;

            }

        }

        if(flag)cout<<sum<<endl;

        else cout<<"data error ."<<endl;

    }

        }