最小生成树 克鲁斯卡尔算法(Kruskal)

题目描述:

输入：

思路:

代码：

#include<bits/stdc++.h>
#define MAX 105
using namespace std;
struct edge{
  int u;
  int v;
  int w;
}e[MAX];
bool cmp(edge x,edge y)
{
    return x.w<y.w;
}
int n,m,f[MAX],sum,c;
//并查集寻找祖先的函数
int getf(int v)
{
    if(f[v]==v)
        return v;
    else
    {
        f[v]=getf(f[v]);
        return f[v];
    }
}
int Merge(int v,int u)
{
    int t1=getf(v);
    int t2=getf(u);
    if(t1!=t2) //判断两个点是否在同一个集合中
    {
        f[t2]=t1;
        return 1;
    }
    return 0;
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
}
int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+m+1,cmp); //按权值从小到大对边进行排序
    init(); //并查集初始化
    c=sum=0;
    //Kruskal算法核心
    for(i=1;i<=m;i++)
    {
        if(Merge(e[i].u,e[i].v))
         {
             c++;
             sum+=e[i].w;
         }
         if(c==n-1)
            break;
    }
    printf("%d\n",sum);
    return 0;
}

 

                                                                                                                                            摘自《啊哈！算法》