每周学点大数据 | No.35缩图法（二）

No.35期

缩图法（二）

Mr. 王：现在我们一步一步来分析。首先，每加入一条边，都会构成一个新的连通分量，或者在已有的连通分量上增加一个点，这意味着每一个强连通分量的大小至少为 2。

由此可知，每一次合并之后产生的图中点的数量和原图中点的数量具有这样的关系

。

而我们最终期待的就是能将所有的点都放进内存中，所以只需要让原图中点的数量去比内存的大小，这个比是 |v| /M 。每一次可以将 v 缩小一半，只要知道缩小多少次就可以将 v 缩小到 M 的大小即可，所以我们要执行递归调用 |v| /M次。

而在每一次递归调用中，我们要做的就是合并那些处在一个连通分量中的点。由于每一次都要寻找和某个点在邻接表中 ID 相邻的那些点与之形成的边，所以在进行合并时，相当于对边进行了一个排序，其复杂度为 sort(E)。

因此，计算出图 G = (V,E) 的连通分量的 I/O 复杂度为

。

小可：这个算法除了被用在判定连通性上，还可以被用来做什么呢？

Mr. 王：其实对图算法非常熟悉的人很快就可以想到，与连通性关联非常紧密的一类问题就是求解最小生成树。

小可：嗯，我知道求解最小生成树的经典算法有 Kruskal 算法和 Prim 算法，求解最小生成树也可以利用我们判定图连通性的框架进行吗？

Mr. 王：只需稍作改动。前面我们在寻找一个节点的临边时，采用的策略就是寻找 ID 和所选择的这个节点的 ID 最接近的顶点；而在求解最小生成树的过程中，我们不再选择 ID 最小的邻居，而是选择权重最小的边。

然后在进行缩图时，压缩后的图中某条边的权值等于该边代表的所有边的权值的最小值。其实这就相当于将两个连通分量用其之间权重最小的那条边连接起来了。

小可：这个思想好像比较接近前面讲过的 Kruskal 算法。

Mr. 王：非常好，当树加入边每一条被合并的边时，实际上加入了可以连接两个连通分量的最小边，而这同时也保障了不会出现两条连通分量被两条边连着。

这是因为我们取过最小的那条边之后，两个连通分量就合为一个，不会再次被合并了。

这个算法的时间复杂度和前面的判断连通性相类似，我们还是尝试将整个图缩小到大小为M，所以要经过

次迭代。在每一次迭代中，我们要去找连接两个连通分量的最小边，要对边集合E进行排序。综合起来，I/O 复杂度也是

。

下面总结一下所提到的图算法给我们的一些启发。时间前向处理技术的思想是，将图问题转化为有向无回路图的估值问题，然后我们就可以利用最经典的表排序方法或者是DAG 估值方法进行求解了。

缩图法正如其所言，在保持不损失我们求解问题所需要的特定信息的情况下，通过不断地迭代缩减图G的规模。在此过程中，在压缩图中递归解决问题。最后我们根据压缩图的解，构造图G的解。

缩图法和时间前向处理都包含着我们在解决数学或者计算机问题时一个很重要的思想或者说手段——“转化”。将难解问题或者未知问题等效转化为一个简单问题或者已知问题去求解，这是一种非常重要的能力。

另外，我们的算法中还隐含着一个思想叫作“自举”，一旦输入（或其部分）规模足够小，即可使用内存算法来求解。

如果输入比较大，则可以通过不断地迭代和压缩，逐渐减小其输入规模，一旦发现下一轮迭代的输入规模已经小到可以放进内存中了，那么接下来的工作就可以交给内存算法去完成。相比磁盘I/O，内存的存取速度是非常快的。

内容来源：灯塔大数据