最小生成树之Kruskal算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最小生成树之Kruskal算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1833字，纯文字阅读大概需要3分钟。

内容图文

介绍：Kruskal算法是用来求加权连通图的最小生成树的一种算法。

对于一个图来说，我们可以选择不同的边而产生不同的树，由于边的选择不一样，每一条边的权值不一样，那我们最后生成出来的树的权值也就不一样，Kruskal算法就是来找怎样选择边才可以使产生的树的权值最小。

思路：现在有一个集合Q，来表示图中的所有的点，有一个集合U，来表示已经生成树中的点，当我们选择了一条边，那我们就将这条边的两个顶点加入到U中，初始时有n个点，m条边。既然我们要求的是生成的树的权值最小，那么我们是不是可以依次选择图中的最小边呢？由于一共用n个点，m条边，那么我们要选的边的最小的个数就是n-1。按照这样的思路，那我们首先要做的就是将这m条边进行从小到大排序，我们只要依次选择这些排好序的边就可以了，当我们已经将某个点已经加入到了我们生成树中，我们就不选择这条边。那么问题就来了，怎样来判断某个点是否已经加入到生成树中？这个时候我们可以使用并查集来判断这个点是否已经加入到了生成树中。 关于并查集：https://www.cnblogs.com/zhoubo123/p/11709160.html

代码实现：

 

#include<iostream>
#include<algorithm>
using namespace std;
int father[1000000];
struct node
{
    int a;//两个顶点 
    int b;
    int w;//权值。 
};
int find(int root)//并查集查找函数 
{
    if(root!=father[root]) father[root]=find(father[root]);//路径压缩。 
    return father[root];
}
int merge(int a,int b)//并查集合并函数 
{
    int aa=find(a);
    int bb=find(b);
    if(aa!=bb) 
    {
        father[bb]=aa;
        return 1;//能够合并返回1 
    }
    return 0;//不能够合并返回0 
}
bool cmp(node a,node b)//排序 
{
    return a.w<b.w;
}
int main()
{
    
        int n,m;
      cin>>n>>m;
      node A[m];
      int cnt=0;//记录选择边的个数 。 
      int sum=0;//生成树的权值。 
      for(int i=0;i<=n;i++)
       father[i]=i;//初始化并查集 。 
       for(int i=0;i<m;i++)
         cin>>A[i].a>>A[i].b>>A[i].w;
        sort(A,A+m,cmp);//排序 
        for(int i=0;i<m;i++)//最小生成树主体。 
        {
            if(merge(A[i].a,A[i].b))//能够合并那么久选择这条边 。 
            {
                 sum+=A[i].w; 
                cnt++;
            }
            if(cnt==n-1)//生成树中有n-1个点时，选择完成 。 
              break;
        }
        cout<<n-1<<" "<<sum;//输出最小生成树的权值。 
    return 0;
} 

 

 

 

内容总结

以上是互联网集市为您收集整理的最小生成树之Kruskal算法全部内容，希望文章能够帮你解决最小生成树之Kruskal算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---