最小生成树-Kruskal算法

article/2025/9/16 11:20:23

数据结构:最小生成树-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;
}