基础算法 | 关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密

有女朋友的忙着帮女朋友清空购物车

有男朋友的忙着叫男朋友帮清购物车

而小编就比较牛逼了

小编沉迷学习，已经无法自拔。

那么今天小编又给大家带来什么好玩的东西呢？

没错

那就是小编通过

夜夜修仙，日日操劳

终于修成的正果

用起来很牛逼，说出去很装逼的

最小生成树

纲要

- 什么是图(network)

- 什么是最小生成树 (minimum spanning tree)

- 最小生成树的算法

1

什么是图

这里的图当然不是我们日常说的图片或者地图。通常情况下，我们把图看成是一种由“顶点(node)”和“边(arc)”组成的抽象网络。各个顶点可以由边连接起来。图的结构可以用来描述多种复杂的数据对象，其应用较为广泛。还是看一个图比较直观：

在各大城市中建设通信网络，如下图所示，每个圆圈代表一座城市，而边上的数字代表了建立通信连接的价格。那么，请问怎样才能以最小的价格使各大城市能直接或者间接地连接起来呢？

我们需要注意两点：

- 最小的价格

- 各大城市可以是直接或者间接相连的

稍稍留心可以发现，题目的要求是，城市只需要直接或者间接相连，因此，为了节省成本，我们稍稍优化一下上述方案如下：

可以看到，我们砍掉了原先在AD，BE之间的两条道路，建设价格自然就降下来了。当然这个方案也是符合我们题目的要求的。

按照国际惯例，这里要说蛋是了。

上面的实例由于数据很简单，优化的方案很easy就看出来了。但在实际中，数据量往往是非常庞大的。所以，我们更倾向于设计一种方法，然后利用计算机强大的运算能力帮我们处理这些数据得出最优的方案。

那么，针对上述问题，我们一起来看看如何应用图的相关知识来实现吧。

2

什么是最小生成树

为了直观，还是用图片给大家解释一下：

- 对于一个图而言，它可以生成很多树，如右侧图2，图3就是由图1生成的。

- 从上面可以看出生成树是将原图的全部顶点以最少的边连通的子图，对于有n个顶点的连通图，生成树有n-1条边，若边数小于此数就不可能将各顶点连通，如果边的数量多于n-1条边，必定会产生回路。

- 对于一个带权连通图，生成树不同，树中各边上权值总和也不同，权值总和最小的生成树则称为图的最小生成树。

3

关于最小生成树的算法

关于最小生成树有两种算法：Prim算法和Kruskal算法。

Prim算法

基本思想：

假设有一个无向带权图G=(V,E)，他的最小生成树为MinTree=(V,T)，其中V为顶点集合，T为边的集合。

求边的集合T的步骤如下：

①令 U={u0}，T={}。其中U为最小生成树的顶点集合，开始时U中只含有顶点u0（u0可以为集合V中任意一项），在开始构造最小生成树时我们从u0出发。

②对所有u∈U，v∈(V – U)（其中u,v表示顶点）的边(u,v)中，找一条权值最小的边(u’,v’)，将这条边加入到集合T中，将顶点v’加入集合U中。

③直到将V中所有顶点加入U中，则算法结束，否则一直重复以上两步。

④符号说明：我们用大写字母表示集合，用小写字母表示顶点元素，用<>表示两点之间的边。

为了更好的说明问题，我们下面一步一步来为大家展示这个过程。

⑴初始状态：U={a} V={b,c,d,e } T={}

⑵集合U和V相关联的权值最小的边是<a,b>，于是我们将b加入U。U={a,b}，V={d,c,e }，T={<a,b>}

⑶此时集合U和V相关联的权值最小的边是<b,c>，于是我们将c加入U。U={a,b,c} ，V={d,e }，T={<a,b>, <b,c>}

⑷显然此时集合U和V中相关联的权值最小的边是<c,d>，于是我们将d加入U。U={a,b,c,d} ，V={e }，T={<a,b>, <b,c>,<c,d>}

⑸最后集合U和V中相关联的权值最小的边是<d,e>，于是将e加入U。U={a,b,c,d,e} ，V={}，T={<a,b>, <b,c>,<c,d>,<d,e>}。

到此所有点访问完毕。

又到了激动银心的看代码时间了

点击文末的“阅读原文”字样可以直接复制黏贴获取代码哦

代码小说明

将城市X标记为visit=true时，就表示该城市加入到集合U，用sum累加记录边的总费用

Kruskal算法

解最小生成树的另一种常见的算法是Kruskal算法，它比Prim算法更直观。

Kruskal算法的做法是：每次都从剩余边中选取权值最小的，当然，这条边不能使已有的边产生回路。手动求解会发现Kruskal算法异常简单，下面是一个例子

先对边的权值排个序：

1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)、8(V3,V6)、10(V5,V6)、12(V3,V5)、15(V4,V5)、20(V0,V1)

首选边1(V0,V4)、2(V2,V6)、4(V1,V3)、6(V1,V2)，此时的图是这样

显然，若选取边8(V3,V6)则会出现环，则必须抛弃8(V3,V6)，选择下一条10(V5,V6)没有问题，此时图变成这样

显然，12(V3,V5)同样不可取，选取15(V4,V5)，边数已达到要求，算法结束。最终的图是这样的

算法逻辑很容易理解，但用代码判断当前边是否会引起环的出现则很棘手。

这里简单提一提连通分量

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中较大的连通子图称为连通分量。

在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。

【算法说明】

为了判断环的出现，我们换个角度来理解Kruskal算法的做法：初始时，把图中的n个顶点看成是独立的n个连通分量，从树的角度看，也是n个根节点。我们选边的标准是这样的：若边上的两个顶点从属于两个不同的连通分量，则此边可取，否则考察下一条权值最小的边。

于是问题又来了，如何判断两个顶点是否属于同一个连通分量呢？这个可以参照并查集的做法解决。它的思路是：如果两个顶点的根节点是一样的，则显然是属于同一个连通分量。这也同样暗示着：在加入新边时，要更新父节点。

憋说话，看代码

点击文末的“阅读原文”字样可以直接复制黏贴获取源代码哦

最后再多说两句

看完了这个

是不是感觉自己又在装逼路上

再次晋级？

古语云：持之以恒，有朝一日，必可成仙。

祝贺大家早日成仙。

END

编辑：邓发珩（华中科技大学管理学院本科一年级，2638512393@qq.com，个人公众号:程序猿声）

金鑫（华中科技大学管理学院硕士一年级, 2383153453@qq.com）

贺兴（华中科技大学管理学院本科三年级，hexing15@gmail.com）

代码: 邓发珩，金鑫，贺兴

指导老师：秦时明岳（professor.qin@qq.com）