【算法】Kruskal最小生成树算法
目录
一、最小生成树
二、Kruskal算法求最小生成树
三、代码
一、最小生成树
什么是最小生成树?
对于一个n个节点的带权图,从中选出n-1条边(保持每个节点的联通)构成一棵树(不能带环),使得所有边的权值和最小,即为最小生成树
要点:
- 选n-1条边
- 要构成一颗树,则树中不能带环
- 节点间要互相连通,即从一个节点能够到达任意一个节点
- 边的权重和最小
二、Kruskal算法求最小生成树
Kruskal算法适用于稀疏图,因为其过程基于边的选择,如果图中的边过多可能导致效率变低
其思路如下:
- 将图中的所有边去掉,只留下节点
- 按照边权的顺序,从权重小的边开始将边回填到图中
- 如果某个边回填到图中会导致带环,则丢弃
- 当回填了n-1条边,得到最小生成树
例如:
这是我们的原图

去掉所有的边

按照权重从小到大回填边



此时发现有两条权重为4的边,选择哪条都可以,这也说明我们的最小生成树并不是唯一的,但最小权重和一定是唯一的

此时有两条权重为5的边,但如果我们把V1和V4之间的边回填的话,就带环了,这是不符合要求的,因此我们选择V2和V3之间的边

此时已经选择了n-1条边,我们的最小生成树就为

三、代码
Kruskal算法的思想很容易理解,但代码实现还是有些难度的
例如我们该如何判断图中是否带环呢?其实很简单,如果在回填某条边时,边两端的节点位于同一个集合中就说明带环。我们可以使用并查集来判断
关于并查集,可以阅读:
【算法】并查集-CSDN博客
https://blog.csdn.net/Eristic0618/article/details/138584962接下来写一道例题练练手
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;#define N 5050
#define M 200020int n, m;
int f[N]; //并查集 struct edge
{int a, b, w;
}e[M];int cmp(struct edge a, struct edge b)
{return a.w < b.w;
}int check(int num) //查询某个节点所在集合的根
{if(f[num] != num) return f[num] = check(f[num]); //压缩路径:将路径上每个节点的父亲都修改为根节点 return num;
}void merge(int a, int b) //合并两个节点所在集合
{if(a == b) //a,b相同 return;f[a] = b; //a的父节点置为b
} bool same(int a, int b) //判断两个节点是否在同一集合
{if(f[a] == f[b]) return true; //a,b父节点相同,说明在同一集合 else return false;
}int Kruskal()
{for(int i = 1; i <= n; i++) //初始化并查集 {f[i] = i;}sort(e, e+m, cmp); //按照边权升序排序 int cnt = 0; //统计当前选择了多少条边 int ans = 0; //最小生成树边权和 for(int i = 0;i < m; i++) //遍历所有边 {int a = e[i].a, b = e[i].b, w = e[i].w;a = check(a), b = check(b);if(same(a, b)) //a与b处于同一连通分量continue;//a与b不处于同一连通分量ans += w; //选择该条边merge(a, b); //将a,b所在连通分量合并 cnt++;if(cnt == n-1) //已选择n-1条边 break;} if(cnt < n-1) //边数不足return -1;return ans;
}void solve()
{cin >> n >> m;for(int i = 0;i < m; i++){int x, y, z;cin >> x >> y >> z;e[i] = {x, y, z}; //存边 }int ans = Kruskal(); //Kruskal算法if(ans == -1) //不连通 cout << "orz" << endl;elsecout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--)solve();return 0;
}
完.
相关文章:
【算法】Kruskal最小生成树算法
目录 一、最小生成树 二、Kruskal算法求最小生成树 三、代码 一、最小生成树 什么是最小生成树? 对于一个n个节点的带权图,从中选出n-1条边(保持每个节点的联通)构成一棵树(不能带环),使得…...
Pocket通常指的是一种特定的凹形或凹槽
在几何和计算机辅助设计(CAD)中,“Pocket”通常指的是一种特定的凹形或凹槽,用于表示在物体表面上挖出的区域。其主要特点包括: 凹形区域:Pocket 是一个在三维模型中内凹的区域,通常从物体的表面…...
Cesium基础-(Entity)-(Billboard)
里边包含Vue、React框架代码 2、Billboard 广告牌 Cesium中的Billboard是一种用于在3D场景中添加图像标签的简单方式。Billboard提供了一种方法来显示定向的2D图像,这些图像通常用于表示简单的标记、符号或图标。以下是对Billboard的详细解读: 1. Billboard的定义和特性 B…...
从0到1,解读安卓ASO优化!
大家好,我是互金行业的一名ASO运营专员,目前是负责我们两个APP的ASO方面的维护,今天分享的内容主要是关于安卓ASO优化方案。 大致内容分为三块: 首先我要讲一下ASO是什么;接下来就是安卓的渠道的选择,安卓…...
go语言中流程控制语句
Go语言中的流程控制语句包括条件判断、循环和分支控制。以下是详细介绍: 1. 条件判断语句 if 语句 Go语言的 if 语句与其他语言类似,支持基本的条件判断。 if 条件 {// 执行代码 }if-else 语句: if 条件 {// 执行代码 } else {// 执行代码…...
k8s 部署 emqx
安装cert-manager 使用Helm安装 helm repo add jetstack https://charts.jetstack.io helm repo update helm upgrade --install cert-manager jetstack/cert-manager \--namespace cert-manager \--create-namespace \--set installCRDstrue如果通过helm命令安装失败&#x…...
CSS.导入方式
1.内部样式 在head的style里面定义如 <style>p1{color: brown;}</style> 2.内联样式 直接在标签的里面定义如 <p2 style"color: blue;">这是用了内联样式,蓝色</p2><br> 3.外部样式表 在css文件夹里面构建一个css文件…...
Linux之nfs服务器和dns服务器
NFS服务器 NFS(Network File System,网络文件系统),NFS服务器可以让PC将网络中的NFS服务器共享的目录挂载到本地端的文件系统中,而在本地端的系统 中看来,那个远程主机的目录就好像是自己的一个磁盘分区一样。 注&am…...
大模型系列——AlphaZero/强化学习/MCTS
AlphaGo Zero无需任何人类历史棋谱,仅使用深度强化学习,从零开始训练三天的成就已远远超过了人类数千年积累的围棋知识。 1、围棋知识 (1)如何简单理解围棋知识 (2)数子法分胜负:https://zhu…...
原生js实现拖拽上传(拖拽时高亮上传区域)
文章目录 drop相关事件说明-MDN演示代码(.html) drop相关事件说明-MDN 演示 代码(.html) <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"…...
python道格拉斯算法的实现
废话不多说 直接开干 需要用到模块 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple math #对浮点数的数学运算函数 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple shapely #提供几何形状的操作和分析,如交集、并集、差集等 pip install -i …...
STM32的hal库中,后缀带ex和不带的有什么区别
在STM32的HAL(硬件抽象层)库中,后缀带“ex”和不带“ex”的文件及其包含的内容存在显著的区别。这些区别主要体现在功能扩展性、使用场景以及API的层次上。 一、功能扩展性 不带“ex”后缀的文件: 这些文件通常包含标准的、核心…...
可观测性三大支柱
目录 可观测性成熟度模型 可观测性三大支柱的具体定义如下 指标 日志 链路 可观测性成熟度模型 可观测性成熟度模型,是一种用于衡量和评估企业软件系统内部可观测性的框架或方法,同 时也是一种用于反馈企业可观测性体系建设成熟度水平的框架或方法…...
【银河麒麟高级服务器操作系统·实例分享】裸金属服务器开机失败分析及处理建议
了解更多银河麒麟操作系统全新产品,请点击访问 麒麟软件产品专区:https://product.kylinos.cn 开发者专区:https://developer.kylinos.cn 文档中心:https://documentkylinos.cn 现象描述 裸金属物理服务器开机卡在EFI stub页面…...
模型剪枝实操
文章目录 实验报告:模型剪枝在图像分类任务中的应用摘要实验方法数据集和预处理模型架构剪枝过程实验设置 实验效果性能对比详细分析 结论 实验报告:模型剪枝在图像分类任务中的应用 摘要 本实验通过模型剪枝技术,对一个图像分类模型进行压…...
网安学习路线!最详细没有之一!看了这么多分享网安学习路线的一个详细的都没有!
零基础小白,到就业!入门到入土的网安学习路线! 在各大平台搜的网安学习路线都太粗略了。。。。看不下去了! 我把自己报班的系统学习路线,整理拿出来跟大家分享了!点击下图,福利! …...
Ubuntu18.04安装vscode1.94.2失败安装vscode1.84.2
系统环境:Ubuntu18.04.6 LTS 自己先去vscode官网下载好最新版本的vscode1.94.2(不下也行,反正最新版也用不了,哈哈) 网址:Visual Studio Code - Code Editing. RedefinedVisual Studio Code is a code ed…...
Redis中Lua脚本的使用场景
Redis 中的 Lua 脚本可以用于多种场景,以下是一些常见的使用场景及其对应的 Java 实现示例。 通过使用 Lua 脚本,可以在 Redis 中实现复杂的逻辑和原子操作,同时利用 Java 客户端(如 Spring Data Redis)方便地执行这些…...
重工业数字化转型创新实践:某国家特大型钢铁企业如何快速落地基于实时数仓的数据分析平台
使用 TapData,化繁为简,摆脱手动搭建、维护数据管道的诸多烦扰,轻量替代 OGG, Kettle 等同步工具,以及基于 Kafka 的 ETL 解决方案,「CDC 流处理 数据集成」组合拳,加速仓内数据流转,帮助企业…...
【linux】手动启动sshd
安装openssh-server修改配置文件启动 以下是在常见的Linux系统中手动开启sshd服务的步骤: 1.安装openssh-server CentOS/RHEL系统 首先,以具有管理员权限的用户(通常是root)登录到系统。检查sshd服务是否已经安装。可以使用以…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
