图论最小生成树

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


最小生成树

最小生成树(Minimum Spanning Tree),简称MST,更详细点叫最小权重生成树,是一副连通加权无向图中一棵权值最小的生成树。对于图,在完全连通的情况下,则拥有生成树。而如果图不连通的话,则拥有多棵生成子树,构成生成森林。

最小生成树正式的定义为:给定一个无向图 $G=(V,E)$ ,$E_{ab}$ ​表示连接顶点a与顶点b的边,有 $E_{ab}∈E $而 $w_{ab}$表示该边的权重若存在T为E的子集(即$ T\subseteq E )且 (V, T) 为树,使得

$$ w(T) =\sum_{E_{ab}∈T} w_{ab}$$

的 $w(T)$ 最小,则此T为G的最小生成树。

利用最小生成树解决实际问题的例子有很多,比如某个镇有十几个小村庄,现要在这些村庄中构建一个通信网络,将每个村庄都连接起来,如何走线能最节省电缆?这就可以用最小生成树解决。

image

Prim算法

Prim(普里姆)算法是一种用于求解最小生成树的算法,通过此算法能搜索到图边集合中某个特定的子集,该子集构成的树能连通图的所有顶点,而且所有边的权重之和最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。

Prim的主要思想是:从图中任意一个顶点开始,每次选择与当前顶点集距离最近的顶点,将对应的边加入到树中,直至所有顶点被处理完。

算法步骤

  • 对于一个加权连通图,其顶点集合为V,边集合为E;
  • 从集合V中任选一个顶点作为初始顶点,将该顶点标为已处理;
  • 已处理的所有顶点可以看成是一个集合T,计算所有与集合T中相连接的顶点的距离,选择距离最短的顶点,将其标记为已处理,并记录最短距离的边;
  • 不断计算已处理的顶点集合T和未处理的顶点的距离,每次选出距离最短的顶点标为已处理,同时记录最短距离的边,直至所有顶点都处理完。
  • 最终,所有记录的最短距离的边构成的树,即是最小生成树。

Prim过程

假如我们现在有一个7个顶点的无向加权图,结构如下图,分别用0-6来表示图的每个顶点,每条边上的数字为对应的权重。

image

为了记录过程状态,引入如下表格,第一列“顶点”表示图的顶点,分别为0到6;第二列“处理标识”表示对应顶点是否已处理,未处理状态为F,已处理状态为T;第三列“权重”表示顶点到顶点的权重,初始值为INF;第四列“顶点”用于描述最小生成树,与第一列的“顶点”组合成最小生成树的边,初始值为-1。

image

现在我们随便选一个顶点3作为初始顶点,将该顶点标记为已处理T,并且权重置为0,因为自己对自己的权重为0。

image

此时已处理集合为{3},检测与顶点3相邻的顶点,先检查(3,1)边的权重,权重设为4,最小生成树另外一个顶点设为3,表示顶点1到顶点3的边。

image

继续检查(3,2)边的权重,权重设为4,最小生成树另外一个顶点设为3,表示顶点2到顶点3的边。

image

类似地,检查(3,4)边的权重,权重设为5,最小生成树另外一个顶点设为3。

image

检查(3,5)边的权重,权重设为1,最小生成树另外一个顶点设为3。

image

对于已处理集合为{3},相邻的所有顶点中,找出权重最小的边,即权重为1的边(3,5),将顶点5的处理标识设为T,并将其加入到已处理集合中,此时集合为{3,5}。

image

对于集合{3,5},检测与它们相邻的顶点,这里注意到因为顶点3上一轮已经检测过了,不必再针对顶点3进行权重检测了,但顶点5能更新之前的权重(可以这样想一下:顶点3到顶点2的权重如果为4,而顶点5到顶点2的权重为2,那么就取权重小的)。于是,检查(5,2)边的权重,权重设为2,最小生成树另外一个顶点设为5,表示顶点2到顶点5的边。

image

接着检测(5,3)边,因为3的处理标识为T,属于已处理集合内的元素,不必检测。

image

继续检测(5,6)边,权重设为3,最小生成树另外一个顶点设为5,表示顶点6到顶点5的边。

image

对于已处理集合为{3,5},相邻的所有顶点中(即除了处理状态为T的其他顶点),找出权重最小的边,

image

所以要找的边是权重为2的边(2,5),将顶点2的处理标识设为T,并将其加入到已处理集合中,此时集合为{2,3,5}。

image

对于集合{2,3,5},检测与它们相邻的顶点,其中顶点3和顶点5上一轮已经检测过了不必再针对它们进行权重检测了。于是检查(0,2)边的权重,权重设为5,最小生成树另外一个顶点设为2,表示顶点2到顶点0的边。

image

继续检测(1,2)边,权重设为1,最小生成树另外一个顶点设为2。

image

接着检测(2,3)边,因为3的处理标识为T,属于已处理集合内的元素,不必检测。

image

继续检测(4,2)边,此时权重为8,而上一轮检测的权重为5,8>5,所以不更新权重,最小生成树另外一个顶点也不更新。这种情况其实就是前面检测顶点3到顶点4的权重更小,也就是说顶点3到顶点4更近,对于集合{2,3,5}来说,到顶点4的权重应该取更小的5。

image

接着检测(2,5)边,因为5的处理标识为T,属于已处理集合内的元素,不必检测。

image

对于已处理集合为{2,3,5},相邻的所有顶点中(即除了处理状态为T的其他顶点),找出权重最小的边,

image

所以要找的边是权重为1的边(2,1),将顶点1的处理标识设为T,并将其加入到已处理集合中,此时集合为{1,2,3,5}。

image

类似地,针对集合{1,2,3,5}进行检测,找到与该集合相连的最小权重的边,记录下对应的边和权重,然后将对应顶点加入到集合中。此轮找到的最小权重为3,对应的边为(0,1),则已处理集合变为{0,1,2,3,5}。

image

继续地,针对集合{0,1,2,3,5}进行检测。此轮找到的最小权重为3,对应的边为(5,6),则已处理集合变为{0,1,2,3,5,6}。

image

最后,针对集合{0,1,2,3,5,6}进行检测。此轮找到的最小权重为3,对应的边为(4,6),则已处理集合变为{0,1,2,3,4,5,6}。

image

此时,所有顶点都已经被处理完了,至此最小生成树的查找工作已经执行完毕。根据第一列的“顶点”和第四列的“顶点”,我们就能够描述出最小生成树了,结果如下。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 图论最小生成树
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏