最小生成树（克鲁斯卡尔算法）

内容导读

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

内容图文

“本模块关联知识点：并查集”

---

首先先引入带权无向图的概念：所谓的带权无向图，就是无向图的边都有权值。

最小生成树即保证每个节点在联通并且没有回路的状态下边的权值之和最小

最小生成树有两种解决方法：1、prime算法；2、kruskal算法；本篇讲解kruskal算法

kruskal算法相较于prime算法更暴力，核心思想是利用快排不断取最小权值的边并通过并查集维护防止产生回路（见下图）

图中最终可得出最小生成树的权值为2+1+1+1+3=7

代码实现（以洛谷P3366为例）

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例

7

本题与上图例题相似，orz输出的判定根据树的节点之间边的数量为节点数-1，这里直接写出实现代码。

#include 
#include 
#include 
#include 
using namespace std;

struct edge
{
    int from,to;
    long long val;
} e[200005];
int pa[5005];

bool cmp(edge a,edge b)
{
    return a.val < b.val;
}

int find_root(int x)
{
    if(pa[x] == x)
        return x;
    return x=find_root(pa[x]);
}

bool vertices_union(int x,int y)
{
    int x_root=find_root(x);
    int y_root=find_root(y);
    if(x_root != y_root)
    {
        pa[x_root]=y_root;
        return true;
    }
    else
        return false;
}

int main()
{
    int n,m;
    long long ans=0;
    cin >> n >> m;
    for(int i=0; i <= n; i++)
        pa[i]=i;
    for(int i=1; i <= m; i++)
        scanf("%d%d%lld",&e[i].from,&e[i].to,&e[i].val);
    sort(e+1,e+m+1,cmp);
    int cont=0;
    for(int i=1; i <= m; i++)
    {
        if(vertices_union(e[i].from,e[i].to))
        {
            ans+=e[i].val;
            cont++;
        }
        if(cont == n-1)
            break;
    }
    if(cont < n-1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
    return 0;
}

内容总结

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

内容备注

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

内容手机端

---