最小生成树Kruskal和Prim算法讨论(2).pdf资源-CSDN文库

版权申诉

139 浏览量 2022-11-06 08:32:44 上传评论收藏 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 集合的顶点

集合还未和 E 相等时，说明循环不变式仍未结束。所以还存在可以添加进 T 的

边。

到了证明边的特性的时候了，一个最小生成树算法的实例已经运行到了普遍

的循环不变式阶段（意味着 T 的点集不为空也不等于 E），这时，我们需要向集

合中添加一条边。

下面就是我自己的一套了“紧缩规则”了，我把已经成为最小生成树的子集

的那部分顶点和边看作一个整体（或者说一个顶点，将它们紧缩成一点），那么

其他的有和这个顶点相连通的顶点所构成的边我把它称为“跨越”子集的边，同

时也可以知道，集合里很正常的会出现“非跨越某一集合”边。通俗的来讲，“跨

越集合的边”会让该集合变大（边数加一，顶点数加一）。

我们要添加进最小生成树子集的顶点（或者边）必须是“跨越”子集 T 的。

然后，如何来确定我们添加进子集的边一定是一课最小生成树的边呢？这时使用

贪心策略是一个好的办法。确保每一次添加进子集的便都是当前满足“跨越”原

则的边中最小的。

这样，每次添加的边就都是属于最小生成树的了。在书中，称这样的边为“轻

边”或者“安全边”。

可以看到，我们用了贪心策略，“每一次子决策都是当前决策集中的最优决

策，会生成一个较优的结果”。后面我会证明在最小生成树生成算法中，这个“较

优”的结果，也是“最优”的。

下面我们来关心具体的实现了，来讨论两个对于图的最小生成树生成的经典

算法 Kruskal 算法和 Prim 算法。这两个算法的策略都是基于我们刚才讨论的“原

始”算法，只不过一个是基于向已知集合添加边，一个是添加点（不过实际它们

没区别）。另一个区别就是 Kruskal 在生成树生成过程中是由森林生成的（Union

Forest），而 Prim 将从一个随机的 Root 开始，最终生成一课 MST，这个过程中，

子集 T 呈现一个生长的姿态。

首先是 Kruskal 算法，我不会给出 Kruskal 的源代码，因为实现 Krukal 还需

要一些现成的数据结构，如果全部实现的话有点累赘，也偏离了讨论 MST 的初

衷。而正是因为 Kruskal 实际实现的程度。它在算法策略比 Prim 要简单。

下面是 Kruskal 的伪代码实现：

KRUSKAL_MST(GRAPH G){

NEW SET(T);

//v is Empty

SORT(G.E)UNINCREASING WITH WEIGHT;

FOR EACH E(v,u) IN INCREASING WITH WEIGHT

IF (SET(v)==SET(u)) CONTINUE;

ELSE UNION(T.V,v,u);

UNION(T.E,(v,u));

RETURN T;

剩余15页未读，继续阅读

评论收藏

内容反馈

版权申诉

G11176593

粉丝: 6643
资源: 3万+

最小生成树Kruskal和Prim算法讨论 (2).pdf

最新资源

最小生成树Kruskal和Prim算法讨论 (2).pdf

最小生成树Kruskal和Prim算法讨论.pdf

最小生成树 prim算法和Kruskal算法实现

cpp-图论算法最小生成树Prim算法和Kruskal算法C实现

最小生成树Kruskal和Prim算法讨论 (2).docx

Prim算法与Kruskal算法求最小生成树

最小生成树之Kruskal和Prim算法的代码实现

图的深度优先搜索，广度优先搜索，最小生成树算法，包括kruskal、prim算法的C++实现代码

最短路径问题(Dijkstra算法)和最小生成树(Kruskal算法和Prim算法).pdf

头歌数据结构图的最小生成树算法

用Prim和Kruskal算法构造最小生成树

prim和kruskal算法求最小生成树

C++ Prim算法Kruskal算法构造可以使n个城市连接的最小生成树

最小生成树算法Kruskal 和 prim

最小生成树kruskal算法并查集版 C语言实现 - Slyar Home

Prim与Kruskal算法的最小生成树matlab实现

C++使用Kruskal和Prim算法实现最小生成树

数据结构 图的最小生成树 C++描述 使用prim算法、kruskal算法

c++源码实现prim最小生成树

python最小生成树kruskal与prim算法详解

Cobalt Strike下载

北京邮电大学计算机考研复试笔试资料

计算机系统-笔记-HUN2021级

cs1.6老版本供下载

合成孔径雷达的经典成像算法cs(matlab)仿真代码（吐血整理，内容全，注释全）

港大CS（MSC）面试整理

合成孔径雷达RD CS OmegaK算法点目标仿真.rar

计算机科学导论原书第二版答案.zip

Cobalt-Strike-4.5

cobaltstrike4.3.zip

最新资源

数据结构图的最小生成树 C++描述使用prim算法、kruskal算法