当前位置：谷粒网 > 在线学习 > 正文

克鲁斯卡尔算法的基本思想 (克鲁斯卡尔算法的应用)

作者：谢颖逸在线学习 2023-05-19 04:54:17 阅读：25

各位网友们好，相信很多人对克鲁斯卡尔算法的基本思想都不是特别的了解，因此呢，今天就来为大家分享下关于克鲁斯卡尔算法的基本思想以及简述克鲁斯卡尔算法算法思想的问题知识，还望可以帮助大家，解决大家的一些困惑，下面一起来看看吧！

克鲁斯卡尔算法的基本思想 (克鲁斯卡尔算法的应用)

本文目录一览

1、最小生成树

2、克鲁斯卡尔算法求最小生成树？

最小生成树

所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G'，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G'的各边权值之和最小，则称G'为图G的最小生成树。由定义我们可得知最小生成树的三个性质：
•最小生成树不能有回路。
•最小生成树可能是一个，也可能是多个。
•最小生成树边的个数等于顶点的个数减一。本文将介绍两种最小生成树的算法，分别为克鲁斯卡尔算法(Kruskal Algorithm)和普利姆算法(Prim Algorithm)。

克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤：
第一步：在带权连通图中，将边的权值排序；
第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。
第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。
下面我用图示法来演示克鲁斯卡尔算法的工作流程，如下图：

克鲁斯卡尔算法求最小生成树？

克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：
1：将图中的n顶点看成是n个集合。解释为，图***有6个顶点，那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。｛a｝,｛b｝等。
2：按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。这是书上的描述，可能有点难理解，这里解释一下：
首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝
3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下：
此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。新的顶点集合为｛a，c｝｛b｝｛e｝｛d，f｝
接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝｛d,f｝｛b,e｝
继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝｛b,e｝
再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！
4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：

版权声明:本文内容由用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。转载请注明出处：https://www.gulizw.com/guli/117245.html

上一篇：关于钱学森的精神 (钱学森的精神和事迹) 下一篇：东芝笔记本事件 (东芝笔记本事件驳论文)

网友评论