当前位置: 首页 > article >正文

图论之cruskal算法(克鲁斯卡尔)

我们已经学了prim算法了,接下来我们来学一下cruskal算法,和prim算法不同的点就在于prim是不断的加结点,而cruskal是不断的加边,不断的加最小的边,我们需要把每个边的权值用结构体存起来,然后排序,从小到大遍历边,不断的加边

如图,我们从权值最小的边开始

当我们把1,2权值为2的边加上去的话,就不符合我们要找生成树的性质了,

那我们怎么维护生成树呢?我们可以把形成生成树的这些结点都放在一个集合里,然后接下来看插入的边的两个结点是不是位于生成树集合里,如果位于生成树集合的话就不连了

OK,那么废话不多说,我们来实现一下代码吧

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct node {
	int x;//结点1
	int y;//结点2
	int z;//权值 
}a[N];
int fa[N];
int find(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void un(int x, int y)
{
	int px = find(x); int py = find(y);
	fa[px] = py;
}
bool cmp(const node& x, const node& y)
{
	return x.z < y.z;
}
int ret = 0;
int cnt = 0;//记录加入了几条边 
int kk()
{
	sort(a + 1, a + 1 + m, cmp);
	for (int i = 1; i <= m; i++)
	{
		int x1 = a[i].x, y1 = a[i].y;
		int z1 = a[i].z;
		int fx = find(x1), fy = find(y1);
		if (fx != fy)
		{
			ret += z1;
			cnt++;
			un(fx, fy);
		}

	}
	return cnt == n - 1 ? ret : INF;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	int r = kk();
	if (r == INF) cout << "orz" << endl;
	else cout << r << endl;




	return 0;
}


http://www.kler.cn/a/588441.html

相关文章:

  • Bash语言的进程管理
  • 数字化转型 - 数据驱动
  • 出现缓存雪崩、缓存穿透、缓存预热、缓存更新和缓存降级的场景,以及如何解决
  • 【数据结构与算法】Java描述:第四节:二叉树
  • DVWA 命令注入从 Low 到 Impossible 教程及源码分析
  • 监控易对各类服务器硬件的广泛支持和深入监控能力
  • pybind11出现的问题
  • 每天五分钟深度学习框架pytorch:常见神经网络层的维度信息总结
  • Linux mount和SSD分区
  • 垃圾回收机制是什么 ?JVM 核心结构?
  • Linux-进程概念
  • 麒麟服务器操作系统Sqlite部署手册
  • 笔记:代码随想录算法训练营day48:739. 每日温度\496.下一个更大元素 I\503.下一个更大元素II
  • 【专项测试】限流测试
  • Java算法OJ(12)
  • Vue 3 组件库主题化与可扩展性深度剖析:设计模式与实现策略 - 构建灵活适应多场景的组件库架构
  • Java缓存String(字符串常量池)、Integer (-128 到 127 )
  • 计算机基础:二进制基础12,十进制数转换为十六进制
  • 联想台式电脑启动项没有U盘
  • 【医学影像 AI】大型语言模型生成 ROP 患者信息材料的能力