大数据 | 大数据基础--算法之亚线性时间算法：近似最小支撑树

亲爱的读者朋友大家晚上好，前两篇文章我们介绍了点集合的直径和连通分量的数量这两个问题，这次我们来分析近似最小支撑树，还是照例，我们先来看一下问题的形式化定义。

定义

已知：\(G=(V,E),\epsilon,d = deg(G)\)，边\((u,v)\)的权重是\(w_{uv}\in \{1,2,\dots,w\}\cup \{\infty\}\)

求：\(\hat{M}\)满足\((1-\epsilon)M\leq \hat{M} \leq (1+\epsilon)M\)，令\(M\)为\(\min_{T spans G}\{W(T)\}\)

分析

MST问题可以在多项式时间求解，例如\(Kruskal\)算法，但是这里并不要求精确的计算结果，而是求出正确结果的一个近似，并且和正确结果之间的误差不超过\(\epsilon \cdot M\)。

为了介绍一个全新的计算最小生成树的算法，我们需要重新利用分解的方法来定义\(M\)，这个很重要，具体的定义以及定理如下所示：

定义：首先我们定义\(G\)的子图\(G^{(i)}=(V,E^{(i)})\)，这里\(E^{(i)} = \{(u,v)|w_{uv}\leq i\}\)，在这个子图上的连通分量的个数为\(C^{(i)}\)，于是我们就可以将\(M\)表示为所有这样的子图的连通分量的数目的和，具体如下面的公式（定理）。

定理：\(M=n-w+\sum_{i=1}^{w-1}{C^{(i)} }\)

证明：设图\(G\)的一个最小生成树为\(MST=(V,E')\)，\(MST\)的子图\(MST^{(i)} = (V',E'^{(i)}),V'=V,E'^{(i)}=\{(u,v)|(u,v) \in E^{(i)} \And (u,v) \in E'\}\)。

设\(\alpha_i\)为\(MST\) 中权重为\(i\)的边的数目，于是\(\sum_{i>1}{\alpha_i}\)表示\(MST\)中所有边权大于\(l\)的边的个数，这个数值加1，应该就是在\(MST\)中将这些边从\(MST\)中去掉之后得到的\(MST^{(l)}\)中的连通分量的个数，而\(MST^{(l)}\)得连通分量的个数应该与\(G^{(i)}\)是一致的，于是我们得到了下面的式子：\(\sum_{i>1}{\alpha_i}=C^{(l)}-1\)。

于是我们就可以用如下的方法计算\(M\)了： \[ \begin{align*} M &= \sum_{i=1}^{w}{i \cdot \alpha_i}=\sum_{i=1}^{w}{\alpha_i} + \sum_{i=2}^{w}{\alpha_i} + \dots + \sum_{i=w}^{w}{\alpha_i}\\ &= C^{(0)}-1 + C^{(1)}-1 + \dots + C^{(w-1)}-1\\ &= n-1+C^{(1)}-1 + \dots + C^{(w-1)}-1\\ &= n-w+\sum_{i=1}^{w-1}{C^{(i)} } \end{align*} \] 证毕

算法

有了上面的定理，我们就可以用之前已经分析过的求连通分量的算法来解决这个问题了，算法过程相当简单，就不再赘述了，我们主要来分析一下算法的精确性，时间复杂度。

精确度

在上一篇文章中我们讲过，\(|C - \hat{C}|\leq \frac{\epsilon\cdot n}{2}\)，于是我们使用绝对值不等式求\(|M-\hat{M}|=|\sum_{i=1}^{w-1}{C^{(i)} }-\sum_{i=1}^{w-1}{\hat{C^{(i)} } }|\leq \sum_{i=1}^{w-1}|{C^{(i)} }-\hat{C^{(i)} }|\leq \frac{\epsilon\cdot w\cdot n}{2}\)，其中\(n\leq M\)，令\(\epsilon'=\frac{\epsilon\cdot w}{2}\)，\(\epsilon\)是一个无穷小，于是\(\epsilon'\)也是一个无穷小，所以\(|M-\hat{M}|\leq \epsilon'M\)满足算法要求的结果。

时间复杂度

也就是运行\(w\)次求解连通分量个数的时间复杂度，\(w\cdot O(d/\epsilon^3)=O(dw^4/\epsilon'^3)\)。

结束

好了，这个算法到这里就结束了，分析的过程稍微有些复杂，学起来还是需要一定的耐心，下周一分析如何计算图的平均度，那将会是一个更加有趣的问题。