最小生成树——克鲁斯卡尔

本文主要是介绍最小生成树——克鲁斯卡尔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

克鲁斯卡尔

克鲁斯卡尔算法是实现图的最小生成树的最常用的算法，适合于求边稀疏的网。

基本思想：

设有一个有n个顶点的联通网N=(V,E),首先构造一个没有边的非联通图T=(V,E)，图中每个顶点自成一个联通分量。当在E中选到具有一条最小权值的边时，若该边的两个顶点落在不同的联通分量上，则将此边加入到T中；否则将此边舍弃，重新选择一条权值最小的边，重复此过程，直到所有顶点都包含进T中。

算法描述：

代码实现：

题目：

题目描述

给出一个带权无向图，求出其最小生成树。保证图连通。

输入

对于每组数据：
第一行输入n,m。表示此图有n(n <= 50000)个点，m(m <= 200000)条边。
接下来m行，每行u,v,w。表示u，v之间有一条权值为w的边。

输出

对于每组数据，输出一个整数代表对应的最小生成树的权值和。

示例输入

示例输出

提示

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>using namespace std;struct node
{int qd;//记录每条边的起点int zd;//记录每条边的终点int quan;//记录权值
};struct node sz[200000];int cmp(struct node i,struct node j)//按权值的从小到大排序
{return i.quan < j.quan;
}int main()
{int n,m,i,j,k,mi,num;int x[50000];while(~scanf("%d%d",&n,&m)){for(i = 1;i <= n;i++)//辅助数组的初始化，即每个点自成一边{x[i] = i;}for(i = 0;i < m;i++){scanf("%d%d%d",&sz[i].qd,&sz[i].zd,&sz[i].quan);}sort(sz,sz+m,cmp);mi = num = 0;for(i = 0;i < m && num < n-1;i++){for(k = sz[i].qd;x[k] != k;k = x[k])//查看起点是否已经存在于联通图{x[k] = x[x[k]];}for(j = sz[i].zd;x[j] != j;j = x[j])//查看终点是否已经存在于联通图{x[j] = x[x[j]];}if(k != j)//若不存在，加进去这条边{x[j] = k;mi += sz[i].quan;num++;}}printf("%d\n",mi);}return 0;
}

这篇关于最小生成树——克鲁斯卡尔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！