贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)
2023-09-11 14:21:03 时间
克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程能够用一个图来表示。这里的图的选择借用了Wikipedia上的那个。很清晰且直观。
首先第一步,我们有一张图,有若干点和边
例如以下图所看到的:
第一步我们要做的事情就是将全部的边的长度排序,用排序的结果作为我们选择边的根据。这里再次体现了贪心算法的思想。资源排序,对局部最优的资源进行选择。
排序完毕后,我们领先选择了边AD。 这样我们的图就变成了
第二步,在剩下的变中寻找。我们找到了CE。这里边的权重也是5
依次类推我们找到了6,7,7。完毕之后,图变成了这个样子。
下一步就是关键了。以下选择那条边呢? BC或者EF吗?都不是,虽然如今长度为8的边是最小的未选择的边。可是如今他们已经连通了(对于BC能够通过CE,EB来连接,相似的EF能够通过EB, BA, AD, DF来接连)。所以我们不须要选择他们。相似的BD也已经连通了(这里的连通线用红色表示了)。所以最后就剩下EG和FG了。当然我们选择了EG。 最后成功的图就是下图:
到这里全部的边点都已经连通了,一个最小生成树构建完毕。
假设要简要得描写叙述这个算法的话就是,首先边的权重排序。(从小到大)循环的推断是否须要选择这里的边。推断的根据则是边的两个顶点是否已经连通,假设连通则继续下一条。不连通就选择使其连通。这个流程还是很清晰明了。
可是在实现的时候,困难的地方在于怎样描写叙述2个点已然连通? 这里用到了并查集做辅助,至于并查集能够到这里去看看。
这里贴出并查集的代码和Kruscal的C++实现:
相关文章
- spring 之 factory-bean & factory-method
- [AWS - DA] CLI & Policies
- [HTML5] aria-label & aria-labelledby
- 机器学习&深度学习基础(机器学习基础的算法概述及代码)
- 【思特奇杯·云上蓝桥-算法训练营】第十一届蓝桥杯大赛第二场省赛试题C&C++ 大学B组真题
- 华为OD机试 - 递增字符串(Java & JS & Python)
- 华为OD机试 - 不含101的数(Java & JS & Python)
- 华为OD机试 - 在字符串中找出连续最长的数字串(含“+-”号)(Java & JS & Python)
- DataScience&ML:基于heart disease心脏病分类预测数据集利用决策数算法基于graphviz/eli5/pdpbox/shap库实现模型可解释性(全局/部分/局部解释)之详细攻略
- ML之LiR&Lasso:基于datasets糖尿病数据集利用LiR和Lasso算法进行(9→1)回归预测(三维图散点图可视化)
- ML之RF&XGBoost:基于RF/XGBoost(均+5f-CrVa)算法对Titanic(泰坦尼克号)数据集进行二分类预测(乘客是否生还)
- ML之LoR&SGD:基于LoR(逻辑回归)、SGD梯度下降算法对乳腺癌肿瘤(10+1)进行二分类预测(良/恶性)
- ML之RF:利用Js语言设计随机森林算法【DT之CART算法(gain index)】&并应用随机森林算法
- DL之RNN:人工智能为你写代码——基于TF利用RNN算法实现生成编程语言代码(C++语言)、训练&测试过程全记录
- ML之LoR&DT&RF:基于LoR&DT(CART)&RF算法对mushrooms蘑菇数据集(22+1,6513+1611)训练来预测蘑菇是否毒性(二分类预测)
- DL之InceptionV2/V3:InceptionV2 & InceptionV3算法的简介(论文介绍)、架构详解、案例应用等配图集合之详细攻略
- DL之GAN&DCGNN&cGAN:GAN&DCGNN&cGAN算法思路、关键步骤的相关配图和论文集合
- 大专&普通本科、搞算法的(蓝桥杯、ACM、天梯赛)-后续成长之路
- 蚂蚁群算法求解最短路径问题(Python&Matlab实现)
- 改进粒子群算法的配电网故障定位(Python&Matlab代码实现)
- 高性能 TCP & UDP 通信框架 HP-Socket v3.2.2 正式公布
- Greenplum 架构详解 & Hash Join 算法介绍
- "伪中国移动client"--伪基站诈骗
- Docker中使用supervisor管理开机自启动(redis && sshd)
- 黏菌优化算法SMA(Python&Matlab完整代码实现)
- Chapter2 ROS通信机制----基础篇(Ⅲ)&ROS常用命令及实操训练