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. 王:是的,一旦图的顶点很多,计算起来就变得非常费时。我们还是要寻找一种随机化法来解决这个问题。接下来我给出的这个算法可以满足:
Mr. 王:下面我们讨论一下这个算法的核心思想。
设C 为连通分量的个数。
对于每一个节点u,我们设n
为u 所在连通分量的节点数。
对于每一个连通分量:
小可:这是为什么呢?
Mr. 王:因为在一个连通分量内部,对于每一个节点而言,其节点数的倒数都是一样的,均为
,在这个连通分量里面又有
个节点,所以相当于
。
Mr. 王:那么对于所有的顶点而言,就有:
你来说说看,这是为什么?
小可:我知道了,因为对于每一个连通分量,都有
只要把所有的连通分量加起来就是包含所有顶点的情况,而在式子的右侧每一个连通分量贡献1,则所有的连通分量之和自然就是C了,即
Mr. 王:很好,接下来我们只要想办法求出
就可以了。解决它的基本思想还是抽样。问题就是,这个抽样怎么做?
如果u 所在连通分量的顶点数很少,那么用图搜索算法遍历它就会很容易,只需要很短的时间。
如果u所在连通分量的顶点数很多,我们计算数精确的
就会变得非常困难,同时
会变得很小,对整个求和的贡献也就变得很小。所以当用图搜索算法遍历一个连通分量产生困难,我们不妨忽略它。
设对的估算值为
这个式子很好地解释了我们之前讨论的情况。即:
当节点数小于
时,我们认为它可以正常完成遍历,显然有
。
当节点数大于
时,我们就认为节点已经多到难以遍历了,就将其估计值定为阈值
,即
。
小可:王老师,我们为什么要取这么奇怪的数呢?
Mr. 王笑了笑说:后面我们还需要这个值来凑
。接下来你想想,当
比较大时,这个估计误差是多少?
小可:估计误差是
。
小于实际值,而且
减去一个正数小于其本身,即
。综合起来就是
。
Mr. 王:不错,我们来整理一下对C 的估计。
我们将对C的估计表示表示为
,那么它的误差就是;
小可:至此,我们成功地证明了误差是有界限的。那么具体的算法又是怎样的呢?
Mr. 王:接下来我们给出具体的算法:
)
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是对连通分量数量的估计,是我们前面已经完成建立的算法。经过前面的分析,这个算法就已经很好理解了。
内容来源:灯塔大数据