【图论】Kruskal算法求最小生成树详解

时间：2025-04-16 20:10:47

Kruskal算法求最小生成树

      • 一、算法学习前先要知道
        • 1.最小生成树概念
        • 2.数据结构：并查集
      • 二、Kruskal算法实现步骤
        • 1.把所有的边排序
        • 2.遍历所有的边
      • 三、Kruskal算法的代码实现

一、算法学习前先要知道

1.最小生成树概念

对于无向图G(V,E),连接所有点V以及边集是E的子集的树称为G的生成树。而边的权值和最小的树即为G的最小生成树。

2.数据结构：并查集

博客链接：并查集介绍以及例题

二、Kruskal算法实现步骤

1.把所有的边排序

把所有的边按照边的长度从小到大排序。对此，我们可以把边的起点，终点，长度封装成结构体，然后重写cmp函数来利用sort函数排序。

2.遍历所有的边

在排序完成后，我们从小到大依次遍历每一条边。此时对于每一条边的两个点u，v会有以下两种情况。

  • 情况1：u和v如果没在连通块中的话，把u和v连通。
  • 情况2：u和v如果在一个连通块中的话，跳过这条边。

以上判断连通块与连通的操作由并查集来完成，而并查集的时间复杂度可以看作常数，所以kruskal算法的时间复杂度为O(m)。

三、Kruskal算法的代码实现

例题链接：Acwing kruskal求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围
1≤n≤1e5,
1≤m≤2∗1e5,
图中涉及边的边权的绝对值均不超过 1000。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

最小生成树板子题，是必须要掌握的例题

//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef  pair<int, int> PII;
const int N = 1e6 + 7;

struct edge  //定义边的结构体
{
	int f, t, w;  //起点，终点，长度
}e[N];

bool cmp(edge a, edge b)  //重写排序函数
{
	return  < ;
}

int p[N];  //并查集祖先数组
int n, m;
int ans = 0;  //答案
int cnt = 0;   //计数器，记录存进最小生成树的边的数量
int find(int x)   //并查集查找函数
{
	if (x != p[x]) p[x] = find(p[x]);
	else return x;
}

void init()  //并查集初始化
{
	for (int i = 0; i <= n; i++)
		p[i] = i;
}

void kruskal()  //算法实现函数
{
	init();
	for (int i = 0; i < m; i++)  //遍历每一条边
	{
		int x = e[i].f, y = e[i].t, z = e[i].w;
		if (find(x) != find(y))  //不连通就连通
		{
			p[find(x)] = find(y);
			ans += z;
			cnt++;
		}
	}

}

void solve()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)   //边的输入
	{
		int a, b, c;
		cin >> a >> b >> c;
		e[i].f = a, e[i].t = b, e[i].w = c;
	}
	sort(e, e + m, cmp);  //排序函数
	kruskal();
	if (cnt == n - 1)   //如果生成树中边小于n-1就说明原图没有最小生成树
		cout << ans << endl;
	else
		cout << "impossible" << endl;
}

int main()
{
	std::ios::sync_with_stdio(false);
	(0), (0);
	solve();
	return 0;
}

作者：Avalon Demerzel，喜欢我的博客就点个赞吧，更多图论与数据结构知识点请见作者专栏《图论与数据结构》

相关文章