最小生成树Kruskal和Prim算法讨论.pdf
版权申诉
116 浏览量
2022-11-06
08:31:35
上传
评论
收藏 995KB PDF 举报
最小生成树的 Kruskal 和 Prim 算法讨论
By 张季伦
最小生成树的定义是在一个图 G（V,E）中，找到一个无回路的子集 T 属于 E，
使得 T 连通所有 V 中的顶点且 T 的边权值和最小。
有定义可知，由于 G`(V,T)没有回路，所以说它是一棵树；边子集 T 使得图
G 成为连通图，所以说 G`(V,T)生成了 G，所以说 G`(V,T)是一个生成树，由于边
权值最小，所以我们叫它最小生成树。
这次主要介绍最小生成树的生成算法，其中又包括 Kruskal 算法和 Prim 算法，
我将给出 Prim 算法的一个简单版本的源代码。
最小生成树的一个实际例子是离散城镇互通问题，其实可以模型化为无向图
的最小生成树问题，初始状态默认了所有城镇都是逻辑上可连通的，那么这是一
个强连通的无向图，然后我们的工作是找到一个方案使得最终修路时所用的材料
最少。也就是总路程长度最短，于是目标就是求这个图的最小生成树。
诶哟突然发现最小生成树和 Disjoint Set 的问题有点相似的，想了解 Disjoint
Sets 的娃儿可以去我的博客看看这一篇很早以前讨论 Disjoint Sets 的文章，写得
比较仔细。（传送门：http://luanluanqc.diandian.com/post/2012-05-08/19418773）
如果你已经稍微懂了最小生成树（Minus Spanning Tree）的概念的话，那让
我们来看看怎么从一个无向图中找到它的 MST。
首先，你要知道一个确定的无向图的 MST 可能是不确定的，也就是可能有
两个不同的生成树然而它们的总权重确实最小且相等的。
然后，我们抛开一切关于计算机实际实现的过程，想一想以最原始的方法如
何求得一个无向图的最小生成树。
好吧，我知道一个图 G（V,E）的 MST 是这样定义的 T（V，E`），MST 与其
图的顶点域是相同的，但是 E`却是 E 的一个子集。于是我这样描述一个求 MST
的原始算法：
我首先定义一个边集合 T，这个 T 在这时是空集。
然后，我向 T 中放入满足如下条件的边 e：
e 满足，当 e 被加入 T 后，T 仍然是一个最小生成树的子集。
当集合 T 顶点集合等于图的顶点集合时，算法运行结束。
这个算法其实只是确定了一个策略，那就是通过不断的向目标结合增加边来
生成最小生成树。而关于接下来的实现的难点就是：我们如何定义“添加进集合
后仍然使集合为最小生成树的子集的边”所拥有的特征。
下面我引入书中的定理加上自己归纳出的一套规则来说明这种特殊的边的
性质，然后我将证明我们算法的正确性。
首先，假设集合 T 已经为空集，这是算法开始时的情况，我们知道，这个图
必然是有最小生成树的，所以说这第一条边必然存在。然后，当 T 集合的顶点
剩余15页未读，继续阅读
资源评论
