每周学点大数据 | No.17最小生成树

No.17期

最小生成树（一）

Mr. 王：我们再来讲一个时间亚线性算法——最小生成树问题。这里先简单介绍一下树的概念。

小可：那什么是树呢？

Mr. 王：树的简单定义，就是一个没有回路的连通无向图。树本身也是一个图，但是它的特点是首先要连通；其次不能有回路。

一棵树

小可：哦，这么说倒是形象了很多，自然界中的树的每个部分都是连在一起的，如果断开了就不是这棵树的部分了。

Mr. 王：如果断开了，也就是说，一个无向图满足无回路，却不满足连通，则称作森林。

森林

小可惊讶地说：连通的叫树，那这种不连通的“树”反而叫森林？

Mr. 王笑着说：如果把森林看成断开的树，可能不好理“解森”林这个名字，但是你仔细想想，是不是森林中的每一个连通分量都是一棵树啊？

小可：好像还真是这样，因为其中的每一个连通分量都是没有回路的、连通的无向图！

Mr. 王：所以森林也可以看成是树的集合。

小可：哈哈，这样就更符合它的定义了。

Mr. 王：树在计算机科学中非常常见而且非常重要。树由于有了这个限制，才有了很多有趣的性质。比如说树中任意两个顶点之间仅存在唯一的一条简单路径。

小可：这个很好理解，因为没有回路啊。

Mr. 王：而且它具有边数等于顶点数-1 这个特点，即：E=V-1。

小可：还真是。

Mr. 王：树只要添加任意一条边，都不再是树；树只要减少任意一条边，也都不再是树。

小可：前者是因为出现了回路，后者是因为图不再连通了。

Mr. 王：很好，掌握了树的基本概念，我们可以继续讨论最小生成树的问题了。

最小生成树是连通的，这一点很显然，我们前面讲过，连通就是任意两个顶点之间都是可达的，虽然它们之间未必有边相连，但是却有一条通路保证可达。

不过在讲解最小生成树问题之前，必须先讲解一下图在计算机中是如何存储的。

小可：嗯，这个的确很重要，要是把整个图形当成一个图片存起来可真是不太现实的，不仅占空间，最重要的是还不好处理。

Mr. 王：其实对于一个图，只需要存储两个要素就可以了，一个是边，一个是顶点。常用的两种存储结构是邻接表和邻接矩阵。这里讲解接下来要用到的邻接矩阵。对于一个图，邻接矩阵的每一行每一列都代表一个顶点，而矩阵中的元素代表的是行代表的点到列代表的点的距离。如果两个顶点之间是没有边的，那么就置为无穷大。好了，我们回到最小生成树问题中，树的每一条边上都有一个权重，也就是这条边的长度。

最小生成树问题有一个很好的例子，比如下面的图：

假设这是一张城市间的地图，图中边的权重就是城市的距离，我们要在城市之间架设电线，以保证两个城市之间连通，但是希望电线的总长度最小，这个问题就是最小生成树问题。其实最小生成树有一个更好的名字，叫作“最小权值生成树”。对于上面的这个图来说，求出的最小生成树就是如下这样的：

求它的经典算法有两个，即Kruskal 和Prim。下面我简单介绍一下Kruskal 算法。

（1）首先将所有的边排序。

（2）不断地取出权值最小的边加入最小生成树中，直到所有的顶点都被连通。同时判断：

如果最小生成树中出现环路了，就将新来的边移除。否则保留它，继续执行第2 步。

小可：哦，这样由于不断取出的边都是最短的边，同时还保证了不出现环路，所以它产生的就是最小生成树吧。

Mr. 王：没错，但是它的复杂度是超过线性的，为O(mlogn)，所以这个算法仅在图比较小的时候能较快地得出结论。

小可：我们还是要寻找亚线性算法。

Mr. 王：对，这里我们提出的亚线性算法基于两个前提：

第一，每个顶点的每个邻居是可以直接访问的。

第二，我们可以随机而均匀地选择节点。这意味着我们可以进行随机均匀的抽样。我们设计的亚线性算法的基本思想是利用特定子图连通分量的数量估计最小生成树的权重。

小可：这个太抽象了，听不懂啊。

Mr. 王笑了笑，说：这个说法的确太复杂了，接下来我用一个简化的例子解释一下。

一棵仅有权值为1 和2 的最小生成树

假设图中所有边的权重都是1 或者2，你考虑一下这个问题：在最小生成树中包含的这些边中，如果将所有边的权重全都减小1，并且记录下减小了多少个1，记为S，那么这个量S代表了什么？

小可：就是最小生成树中包含的边数。

Mr. 王：那这个边数应该是多少呢？

小可：要把图中的n 个顶点全部连接起来，3 个顶点至少需要2 条边，4 个顶点至少需要3 条边，那么n 个顶点至少需要n-1 条边！

Mr. 王：很好，这也恰好是树中顶点数和边数的关系。在一棵树中，边数等于顶点数-1。

如果将最小生成树的边数表示成这个式子，那么对于我们做出假设的这个图，最小生成树的权重=#N1+#N2。其中的#Ni 表示最小生成树中权重至少为i 的边的数量，那么最小生成树的权重可以表示成什么？

小可：因为最小生成树有n-1 条边，所以就是n-1+#N2

Mr. 王：好，我们现在只把权值为1 的那些边加进来了，这可能会导致什么？

小可：有很多节点是由边权为2 的边连接着的，如果只考虑边权为1 的边，最小生成树就不连通了。

Mr. 王：没错，的确会出现这样的问题。前面我们已经给这些不连通的树起了名字，叫作连通分量。那么这些连通分量组成最小生成树要用什么来连接呢？需要多少条边呢？

小可：要用权值为2 的那些边。如果这些连通分量都看作是顶点的话，比如有m 个顶点，那么就需要m-1 条边！这个构成一个连通图是一致的。

Mr. 王：非常好，我们的结果就可以表示成：

n-1+ 权重为1 的边构成的导出子图的连通分量数-1，如果这个图中的边权有1、2、3，那么其做法和上面的也是一样的，只是此时我们要考虑的是#N1、#N2、#N3。

内容来源：灯塔大数据