---

最小生成树专题2 最小生成树-Kruskal算法

原创 于 2023-10-26 17:27:45 发布 · 粉丝可见 · 163 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/134061034

题目：

样例1：

bash<br/>4 5<br/>0 1 3<br/>0 2 2<br/>0 3 3<br/>2 3 1<br/>1 2 1<br/>

4

样例2：

bash<br/>3 1<br/>0 1 1<br/>

-1

思路：

由题意，我们看一下数据，可以知道，朴素版的最小生成树，是使用 二维数组存储的对应结点和边权关系，由于数据过大，二维数组存储不了了，又因为朴素版中，使用了嵌套循环，这种嵌套循环，数据一大，时间复杂度也就高了起来，这里的 m 是 10^5 ，最坏情况的时候 ，嵌套循环后，时间复杂度是 10^10 ，会导致 TLE。

所以我们这里，克鲁斯卡尔算法，就可以有效的避免了空间问题，和时间问题，结合使用并查集查询，可以有效率的解决掉这个问题了。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int n,k;
 
// 定义结点之间的边权关系结构体数组，
struct Edge
{
	int a,b,w;
	// 重载结构体排序规则，将边权少的放前面
	inline bool operator<(const Edge&t)const
	{
		return w < t.w;
	}
}edge[N];
 
int p[N];	// 集合点数组
 
// 并查集 查找根节点函数
inline int find(int &x)
{
	int t = x;	// 记录查找点
	// 查找根节点
	while(x != p[x])
	{
		x = p[x];
	}
	p[t] = x;	//剪枝查找路径，记录对应查找点的根节点
	return x;	// 返回根节点	
}
 
// 克鲁斯卡尔算法函数
inline int Kruskal()
{
	int ans = 0,cnt = 0;	// 定义最小生成树 ans数值，以及 cnt 经过的边
	// 遍历每一条边
	for(int i = 0;i < k;++i)
	{
		// 取出对应的两个结点
		int a = edge[i].a;
		int b = edge[i].b;	
		
		// 查找对应的两个结点是否以及遍历过
		a = find(a),b = find(b);
		if(a != b)
		{
			// 如果没有遍历过，那么放在同一个集合
			p[a] = b;
			ans += edge[i].w;	// 累加最小边权，即累加最小生成树 ans 数值
			++cnt;	// 记录走动的 边   
		}
	}
	// 如果走动的 边数 不足够 结点数 - 1 说明有孤立点，没有最小生成树
	if(cnt < n - 1) return -1;	// 返回 -1
	return ans;	// 返回最小生成树数值
}
 
inline void solve()
{
	cin >> n >> k;
	for(int i = 0;i < k;++i)
	{
		int a,b,w;
		cin >> a >> b >> w;
		edge[i] = {a,b,w};	// 存储好对应的结点之间的边权关系
	}
	// 排序最小边
	sort(edge,edge + k);
	
	// 初始化集合点
	for(int i = 0;i <= n;++i)p[i] = i;
	
	// 计算 克鲁斯卡尔算法 并返回答案
	cout << Kruskal() << endl;
}
 
int main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：