图论最小生成树

推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种 排序 等等几十篇的样子。

最小生成树

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

最小生成树正式的定义为：给定一个无向图 ， 表示连接顶点a与顶点b的边，有 ，而 表示该边的权重，若存在T为E的子集(即 )且 (V, T) 为树，使得

的 最小，则此T为G的最小生成树。

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

Prim算法

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

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

算法步骤

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

Prim过程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、 mysql 协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇

跟我交流，向我提问：

欢迎关注：