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

【算法】Kruskal最小生成树算法

目录

一、最小生成树

二、Kruskal算法求最小生成树

三、代码


一、最小生成树

什么是最小生成树? 

对于一个n个节点的带权图,从中选出n-1条边(保持每个节点的联通)构成一棵树(不能带环),使得所有边的权值和最小,即为最小生成树

要点:

  • 选n-1条边
  • 要构成一颗树,则树中不能带环
  • 节点间要互相连通,即从一个节点能够到达任意一个节点
  • 边的权重和最小


二、Kruskal算法求最小生成树

Kruskal算法适用于稀疏图,因为其过程基于边的选择,如果图中的边过多可能导致效率变低

其思路如下:

  • 将图中的所有边去掉,只留下节点
  • 按照边权的顺序,从权重小的边开始将边回填到图中
  • 如果某个边回填到图中会导致带环,则丢弃
  • 当回填了n-1条边,得到最小生成树

例如:

这是我们的原图

去掉所有的边

按照权重从小到大回填边

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

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

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


三、代码

Kruskal算法的思想很容易理解,但代码实现还是有些难度的

例如我们该如何判断图中是否带环呢?其实很简单,如果在回填某条边时,边两端的节点位于同一个集合中就说明带环。我们可以使用并查集来判断

关于并查集,可以阅读:

【算法】并查集-CSDN博客icon-default.png?t=O83Ahttps://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算法求最小生成树 三、代码 一、最小生成树 什么是最小生成树&#xff1f; 对于一个n个节点的带权图&#xff0c;从中选出n-1条边&#xff08;保持每个节点的联通&#xff09;构成一棵树&#xff08;不能带环&#xff09;&#xff0c;使得…...

Pocket通常指的是一种特定的凹形或凹槽

在几何和计算机辅助设计&#xff08;CAD&#xff09;中&#xff0c;“Pocket”通常指的是一种特定的凹形或凹槽&#xff0c;用于表示在物体表面上挖出的区域。其主要特点包括&#xff1a; 凹形区域&#xff1a;Pocket 是一个在三维模型中内凹的区域&#xff0c;通常从物体的表面…...

Cesium基础-(Entity)-(Billboard)

里边包含Vue、React框架代码 2、Billboard 广告牌 Cesium中的Billboard是一种用于在3D场景中添加图像标签的简单方式。Billboard提供了一种方法来显示定向的2D图像,这些图像通常用于表示简单的标记、符号或图标。以下是对Billboard的详细解读: 1. Billboard的定义和特性 B…...

从0到1,解读安卓ASO优化!

大家好&#xff0c;我是互金行业的一名ASO运营专员&#xff0c;目前是负责我们两个APP的ASO方面的维护&#xff0c;今天分享的内容主要是关于安卓ASO优化方案。 大致内容分为三块&#xff1a; 首先我要讲一下ASO是什么&#xff1b;接下来就是安卓的渠道的选择&#xff0c;安卓…...

go语言中流程控制语句

Go语言中的流程控制语句包括条件判断、循环和分支控制。以下是详细介绍&#xff1a; 1. 条件判断语句 if 语句 Go语言的 if 语句与其他语言类似&#xff0c;支持基本的条件判断。 if 条件 {// 执行代码 }if-else 语句&#xff1a; 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;">这是用了内联样式&#xff0c;蓝色</p2><br> 3.外部样式表 在css文件夹里面构建一个css文件…...

Linux之nfs服务器和dns服务器

NFS服务器 NFS&#xff08;Network File System&#xff0c;网络文件系统)&#xff0c;NFS服务器可以让PC将网络中的NFS服务器共享的目录挂载到本地端的文件系统中&#xff0c;而在本地端的系统 中看来&#xff0c;那个远程主机的目录就好像是自己的一个磁盘分区一样。 注&am…...

大模型系列——AlphaZero/强化学习/MCTS

AlphaGo Zero无需任何人类历史棋谱&#xff0c;仅使用深度强化学习&#xff0c;从零开始训练三天的成就已远远超过了人类数千年积累的围棋知识。 1、围棋知识 &#xff08;1&#xff09;如何简单理解围棋知识 &#xff08;2&#xff09;数子法分胜负&#xff1a;https://zhu…...

原生js实现拖拽上传(拖拽时高亮上传区域)

文章目录 drop相关事件说明-MDN演示代码&#xff08;.html) drop相关事件说明-MDN 演示 代码&#xff08;.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 #提供几何形状的操作和分析&#xff0c;如交集、并集、差集等 pip install -i …...

STM32的hal库中,后缀带ex和不带的有什么区别

在STM32的HAL&#xff08;硬件抽象层&#xff09;库中&#xff0c;后缀带“ex”和不带“ex”的文件及其包含的内容存在显著的区别。这些区别主要体现在功能扩展性、使用场景以及API的层次上。 一、功能扩展性 不带“ex”后缀的文件&#xff1a; 这些文件通常包含标准的、核心…...

可观测性三大支柱

目录 可观测性成熟度模型 可观测性三大支柱的具体定义如下 指标 日志 链路 可观测性成熟度模型 可观测性成熟度模型&#xff0c;是一种用于衡量和评估企业软件系统内部可观测性的框架或方法&#xff0c;同 时也是一种用于反馈企业可观测性体系建设成熟度水平的框架或方法…...

【银河麒麟高级服务器操作系统·实例分享】裸金属服务器开机失败分析及处理建议

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer.kylinos.cn 文档中心&#xff1a;https://documentkylinos.cn 现象描述 裸金属物理服务器开机卡在EFI stub页面…...

模型剪枝实操

文章目录 实验报告&#xff1a;模型剪枝在图像分类任务中的应用摘要实验方法数据集和预处理模型架构剪枝过程实验设置 实验效果性能对比详细分析 结论 实验报告&#xff1a;模型剪枝在图像分类任务中的应用 摘要 本实验通过模型剪枝技术&#xff0c;对一个图像分类模型进行压…...

网安学习路线!最详细没有之一!看了这么多分享网安学习路线的一个详细的都没有!

零基础小白&#xff0c;到就业&#xff01;入门到入土的网安学习路线&#xff01; 在各大平台搜的网安学习路线都太粗略了。。。。看不下去了&#xff01; 我把自己报班的系统学习路线&#xff0c;整理拿出来跟大家分享了&#xff01;点击下图&#xff0c;福利&#xff01; …...

Ubuntu18.04安装vscode1.94.2失败安装vscode1.84.2

系统环境&#xff1a;Ubuntu18.04.6 LTS 自己先去vscode官网下载好最新版本的vscode1.94.2&#xff08;不下也行&#xff0c;反正最新版也用不了&#xff0c;哈哈&#xff09; 网址&#xff1a;Visual Studio Code - Code Editing. RedefinedVisual Studio Code is a code ed…...

Redis中Lua脚本的使用场景

Redis 中的 Lua 脚本可以用于多种场景&#xff0c;以下是一些常见的使用场景及其对应的 Java 实现示例。 通过使用 Lua 脚本&#xff0c;可以在 Redis 中实现复杂的逻辑和原子操作&#xff0c;同时利用 Java 客户端&#xff08;如 Spring Data Redis&#xff09;方便地执行这些…...

重工业数字化转型创新实践:某国家特大型钢铁企业如何快速落地基于实时数仓的数据分析平台

使用 TapData&#xff0c;化繁为简&#xff0c;摆脱手动搭建、维护数据管道的诸多烦扰&#xff0c;轻量替代 OGG, Kettle 等同步工具&#xff0c;以及基于 Kafka 的 ETL 解决方案&#xff0c;「CDC 流处理 数据集成」组合拳&#xff0c;加速仓内数据流转&#xff0c;帮助企业…...

【linux】手动启动sshd

安装openssh-server修改配置文件启动 以下是在常见的Linux系统中手动开启sshd服务的步骤&#xff1a; 1.安装openssh-server CentOS/RHEL系统 首先&#xff0c;以具有管理员权限的用户&#xff08;通常是root&#xff09;登录到系统。检查sshd服务是否已经安装。可以使用以…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...