数据结构:最小生成树-Kruskal算法

什么是最小生成树，最小生成树就是求图中把所有点都访问到的最短路径的长度
Kruskal算法采用的是边贪心思想，我们先大概讲一下它的大概思想，首先我们先假设先隐藏所有的边，这样每个点会成为一个连通块。

步骤1：先对图中所有的边按照权值进行排序
步骤2：如果当前这条边的两个顶点不在一个连通块里面，那么咋就用并查集的Union函数把他们合并在一个连通块里面(也就是把他们放在最小生成树里面)，如果再在一个并查集里面，我们就舍弃这条边，不需要这条边。
步骤3：一直执行步骤2，知道当边数等于定点数的数目减去1，那就说明这n个顶点就连合并在一个集合里面了；如果边数不等于顶点数目减去1，那么说明这些边就不连通。

现在，我们通过几个图来看一下，Kruskal求最小生成树是怎么求的。不要眨眼啊！！！！

1.我们看一下这个图，把所有的边进行排序，先假设把所有边先隐藏掉，排完序后的边的权值是：10 12 14 16 18 22 24 25 28；
2.我们先找到的是权值10的边的两个顶点是0和5，先将0和5这两条边合在一个集合里面，并且连上一条边。

2.找到第二个最小的边的权重是12，连接的是2和3，现在我们把这两条边连起来，并且合并在一个集合里面。

3.同理，把1和6连接起来并合并

4.同理，把1和2连接起来并合并

5.这个时候权值是18，注意一下，因为6和3已经在一个集合里面，我们就直接跳过，不用处理。

6.下一个连接和合并是3和4

7.注意一下，此时4和6在一个集合里面了，我们直接跳过
8.我们连接并合并4和5两个顶点

此时到这里面，我们的边数等于顶点数目减去1，退出。
这个就是最小生成树的生成过程，可以用个ans记入每次连边时候的权值，就能得到最小的权值。
先给个题目连接：https://www.luogu.com.cn/problem/P3366
可以自己先尝试一下》》》》
下面附上我的代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int father[maxn];//father数组存放的是父亲结点
struct Edge{
	int u;//左端点
	int v;//右端点
	int dis;//权值
}ed[maxn];
bool cmp(Edge a,Edge b){//结构体排序
	return a.dis < b.dis;
}
void init(int n){//初始化
	for(int i=1;i<=n;i++) father[i] = i;
}
int find_father(int x){//并查集核心操作
	if(x==father[x]) return x;
	int temp = find_father(father[x]);//路径压缩
	return temp;
}
int Kruskal(int n,int m){
	int ans = 0;//记入最小生成树的权值
	int num_Edge = 0;//边的数目
	for(int i=0;i<m;i++){
		int fu = find_father(ed[i].u);//找最终父亲
		int fv = find_father(ed[i].v);//找最终父亲
		if(fu!=fv){
			father[fu] = fv;//合并
			ans+=ed[i].dis;
			num_Edge++;
			if(num_Edge==n-1) break;
		}
	}
	if(num_Edge!=n-1) return -1;//退出条件
	else return ans;
}
int main(){
	int n,m;
	cin>>n>>m;
	init(n);
	for(int i=0;i<m;i++) cin>>ed[i].u>>ed[i].v>>ed[i].dis;//输入
	sort(ed,ed+m,cmp);//排序
	cout<<Kruskal(n,m);
	return 0;
}
复制

感谢张大佬的审核！！！

推荐内容