每周学点大数据 | No.18最小生成树（二）
No.18期
最小生成树（二）
Mr. 王：接下来我们讨论一般的情况。在一般的情况中，我们先定义一些量以方便讨论。
Gi ：G 中包含所有权重小于i 的边的子图。
Ci ：Gi 中的连通分量数。
令βi 为最小生成树中权重大于i 的边的个数，那么最小生成树的权重之和就可以表示成
这是一个很朴素的累和。
由我们前面讨论的结果可以得出最小生成树中权重大于i 的边数为Ci-1。
其中的常数1 可以提出来，结果就是：
这里还有一个特殊的C0，它的值就是所有的边，也就是n，我们把它提出来，就可以得到最终的结论：
你来说说看，这个过程建立了哪两个量之间的关系？
小可：建立了最小生成树的权重WMST(G)和连用分量的个数Ci之间的关系。
Mr. 王：很好，此时问题就转变成了，当拿到一个图之后，如何快速地估计这个图的连通分量的个数。当先来看看基础算法和它存在的问题。我们定义问题为
输入：图G=(V, G)，有n 个顶点，表示为邻接矩阵，节点最大度为d。
输出：连通分量的个数。
对于经典算法，简单来说，就是对于每个顶点，我们都要研究其邻居节点，这样它的时间复杂度为W(dn)。
小可：这样它就不是一个亚线性算法了。
Mr. 王：是的，一旦图的顶点很多，计算起来就变得非常费时。我们还是要寻找一种随机化法来解决这个问题。接下来我给出的这个算法可以满足：
- 用来估计连通分量个数#CC。
- Pr（#CC）。
- 同时在时间复杂度上和n无关。
Mr. 王：下面我们讨论一下这个算法的核心思想。
设C 为连通分量的个数。
对于每一个节点u，我们设n
为u 所在连通分量的节点数。
对于每一个连通分量：
小可：这是为什么呢？
Mr. 王：因为在一个连通分量内部，对于每一个节点而言，其节点数的倒数都是一样的，均为
，在这个连通分量里面又有
个节点，所以相当于
。
Mr. 王：那么对于所有的顶点而言，就有：
你来说说看，这是为什么？
小可：我知道了，因为对于每一个连通分量，都有
只要把所有的连通分量加起来就是包含所有顶点的情况，而在式子的右侧每一个连通分量贡献1，则所有的连通分量之和自然就是C了，即
Mr. 王：很好，接下来我们只要想办法求出
就可以了。解决它的基本思想还是抽样。问题就是，这个抽样怎么做？
如果u 所在连通分量的顶点数很少，那么用图搜索算法遍历它就会很容易，只需要很短的时间。
如果u所在连通分量的顶点数很多，我们计算数精确的
就会变得非常困难，同时
会变得很小，对整个求和的贡献也就变得很小。所以当用图搜索算法遍历一个连通分量产生困难，我们不妨忽略它。
设对的估算值为
这个式子很好地解释了我们之前讨论的情况。即：
当节点数小于
时，我们认为它可以正常完成遍历，显然有
。
当节点数大于
时，我们就认为节点已经多到难以遍历了，就将其估计值定为阈值
，即
。
小可：王老师，我们为什么要取这么奇怪的数呢？
Mr. 王笑了笑说：后面我们还需要这个值来凑
。接下来你想想，当
比较大时，这个估计误差是多少？
小可：估计误差是
。
小于实际值，而且
减去一个正数小于其本身，即
。综合起来就是
。
Mr. 王：不错，我们来整理一下对C 的估计。
我们将对C的估计表示表示为
，那么它的误差就是；
小可：至此，我们成功地证明了误差是有界限的。那么具体的算法又是怎样的呢？
Mr. 王：接下来我们给出具体的算法：
- CC（G，d，
）
1.
2.随机选择点u
3. 从u开始BFS,将访问到的顶点存点到排序队列L中，访问完连通分量或L=2/
时停止，
4.
5. 返回C=s/N×n
小可：第1行我就没有看懂，
是怎么回事呢？
Mr. 王：这个表示抽样要与
同阶，但是具体怎么抽取，接下来我们还会进一步讨论。现在你只要知道这一步是进行抽样即可。
第2行很简单，我们随机选取抽样中的一个点。
在第3行中，我们用选取的这个点，在连通分量内执行图搜索算法，将访问到的顶点都放在排序队列L里面，如果不能将队列填满到
，我们就取队列内元素的个数nu；否则，一旦L的长度为
，我们就将的估计值取
。
第4行，将估计值进行累加。
第5行，根据前面的推导，给出一个对连通分量个数的估计，
。这里体现的就是一个样本估计总体的思想。
我们来看看整个算法的时间复杂度：
。
小可：这个值可是够复杂的。
Mr. 王：你别看它的形式很复杂，但从式子中不难看出，复杂度与图的大小是无关的，说明这是一个很好的亚线性算法。我来仔细解释一下这个复杂度的构成。
首先，整个外侧的循环是与
同阶的，而在每一次循环中，最多就处理
个节点；其次，当我们把节点放进L中时，由于这个L是一个排序队列，将一个新的元素插入一个排序队列中的时间效率为
,所以相乘后的结果就是
。
Mr. 王：好了，到现在为止，我们已经设计和分析了对连通分量进行估计的近似算法：
其中，CC是对连通分量数量的估计，是我们前面已经完成建立的算法。经过前面的分析，这个算法就已经很好理解了。
内容来源：灯塔大数据