重谈MST及Kruskal算法
算法 kruskal MST
2023-09-11 14:20:16 时间
重谈MST及Kruskal算法
当初学MST(Minimum Spanning Tree)最小生成树的时候,还是懵懵懂懂,不求慎解。所以只记下了模板,狂拍了几道板子题和板子题加一点点变形的题目。所以今天来温故而知新一下。
MST的一些性质
这里有一个定理,就是MST一定包含全图权值最小的边。用反证法可证明这个定理。如果有一条边不在MST中但是比MST的所有边权更小,那么这条边可以和MST的一条路径一起构成一个环,用这条边任意替换环里的一条边,可以得到一个更M的MST。
证毕。
所以放出一个大推论(哦!好难)
给定一张无向图\(G=(V,E)\),从\(E\)中选出\(k<n-1\)条边构成\(G\)的一个生成森林,若再从剩下的\(m-k\)条边中选\(n-1-k\)条添加到生成森林中使之成为\(G\)的MST,则该MST一定包含这\(m-k\)条边中链接生成森林的两个不连通节点的权值最小边。
看起来很难,但是其实这就是一个贪心策略。
其实求MST的过程就是从中选边把所有节点连起来,并且要求边权和最小的一个过程。那么从头开始,现在有一堆散点,我们开始连,肯定要挑选最小的边开始,然后依次取最小,如果可以加(即加边不构成环),就继续添加,否则就跳过。这么一个贪心策略肯定是最优的。
Kruskal算法
于是,基于上述策略,通过模拟就可以得到Kruskal算法,也就是把边录入之后进行排序,用并查集维护是否出现环,之后从小到大逐次向MST中添加即可。添加到n-1条边时即求出MST。
代码略。
相关文章
- java实现Kruskal算法
- Java实现 蓝桥杯VIP 算法提高 邮票面值设计
- Java实现 蓝桥杯VIP 算法提高 传染病控制
- 最小生成树-Prim算法和Kruskal算法
- 重新整理数据结构与算法——单双链表模拟队列[四]
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.57】引入可形变卷积
- Algorithm:【Algorithm算法进阶之路】之十大经典排序算法
- CV之IS:基于pixellib库和coco数据集且加载.h5文件利用Mask RCNN算法实现图像实例分割简单代码全实现(以热播电视剧《庆余年》视频片段为例)案例应用
- Interview:算法岗位面试—10.11下午—上海某公司算法岗位(偏数据分析,证券金融行业)技术面试考点之sqlserver语言相关考察点复习
- 判断四张扑克牌能否凑成24点游戏算法
- Java 地下迷宫·算法·(ACM/蓝桥杯)·递归解法
- leetcode算法第四题
- 基于麻雀算法优化的Tsallis相对熵图像多阈值分割 -附代码
- 克鲁斯卡尔算法(Kruskal算法)求最小生成树
- Kruskal算法
- AcWing算法学习第三节---高精度问题.
- 机器学习知识经验分享之三:基于卷积神经网络的经典目标检测算法