每周学点大数据 | No.34缩图法（一）

No.34期

缩图法（一）

Mr. 王：接下来我们再谈一种常用于磁盘上存储的图的思想，叫作缩图法。我们不得不设计磁盘算法，重要原因就是内存存不下特别大的图。

所以一些基本的考虑就是，我们能不能试着把图变得小一点，使之能被放进内存中。如果经过若干次I/O 之后，使得图剩下的部分可以被放进内存中，那么处理也就变得容易多了。

小可：哦，“缩图法”名字听起来也好像是这个思想。具体怎么做呢？

Mr. 王：我们来看这样一个问题：判定一个特别大的图的连通性。显然这个大图会被存储在外存中。

Mr. 王：首先我们试着给出一个半外存算法。

小可：这个“半外存”怎么解释呢？

Mr. 王：整个图的所有边和点可能是内存存不下的，但是如果图中的所有顶点都可以存放在内存中，那么对我们的处理将会相当有利。

这在实际情况中还是比较常见的，因为对于比较稠密的图来说，边要比顶点多得多。

半外存的连通性判定是这样做的：首先，内存可以存得下所有的顶点，我们先将所有的顶点都放进内存中。接下来，我们从磁盘中读取边，逐条地把边放到内存中。

每读取一条边，都做一个处理，就是将这条边删掉，然后将此边连接的两个顶点合成为一个顶点。

我们之所以可以这么做，是因为图的连通性不会因为这种操作而被破坏，原来连通的部分依然连通，不连通的地方也就相应地没有边了。

小可：哦，这样不断地做下去，一个连通分量内的点不久就会被缩成一个点。最后当所有的边都被处理之后，如果内存中剩下的是一个点，则说明整个图都是连通的；否则就不是连通的。这个方法真巧妙。

Mr. 王：是的，这种半外存算法做到了无须让内存保存所有的边和点，内存只需要保存所有的顶点和图上的一条边就可以了。每当一条边处理结束后，我们就丢掉它。现在来看看算法的复杂度如何。

小可：首先，算法预处理时，要将所有的顶点扫描一遍，需要 O(scan(|V|)) 次 I/O。然后，在算法执行的过程中，需要扫描所有的边，所以需要 O(scan(|E|)) 次 I/O。

Mr. 王：嗯，所以整个算法的 I/O 复杂度就是O(scan(|V|+|E|))。但是这里需要注意，可以采用这种半外存算法的重要前提就是 |V|<M。

也就是说，所有的顶点必须都能放进内存中，这种做法及其相应的复杂度才是正确的。

小可：不过在实际情况中，也会有很多 |V|>M 的情况，对于那些真的大到连顶点都不能全放进内存中的图怎么办呢？

Mr. 王：嗯，接下来我们就谈一谈对一般情况怎么处理。

当我们需要处理一个图时，首先要做一个判定：如果图的顶点可以全部放进内存中，就可以使用前面提到的半外存算法；如果不能，就尝试下面这种方法，先说说它的思想。

首先我们期望找到 G 的一个简单连通子图，然后尝试对连通子图进行收缩，使得这个子图的节点数变少。

这是一般情况下的图。假设这是比较大的图，内存中不能存储下所有的节点。我们为了进行处理，只能先选取一部分边放入内存，这一部分边要尽可能多地放入内存中。

假设放入内存中的这些点就是所有的点，然后执行前面的半外存算法，尽可能多地将边装入内存中。

这时我们就能有效地发现一些连通分量。下一步是进行缩图，将这些边从内存中剔除；相应地，对内存中已经存在的连通分量进行合并，合并成一个新的点。

接下来进行下一轮迭代，将已经合并完的点当作新的顶点，继续将外存中的边逐步加入到内存中。

小可：此时顶点的命名已经发生了改变，是不是还要记住这些合并顶点间的对应关系呢？

Mr. 王：没错，比如新的顶点 A 和 B 之间的边，外存中保存的数据中并没有 A 和 B 顶点间的边，只有 ef 和 dc这样的边，所以还要有机制来记住 e、 f 这两个顶点之间的边，在下一轮迭代中，是 A、 B 两个顶点之间的边。

持续地迭代下去，就可以求出结果了。下面我们来总结一下，在一般情况下，图的连通性判定是怎么做的。

第 1 步：对于每一个点找到其最小的邻居，如果图是使用邻接表来表示的话，就非常的容易，直接搜索其邻接表就可以了。

第 2 步：计算图 H 由选定的边导出的连通分量，这是我们前面描述算法的过程中主要完成的一项工作。

第 3 步：将每一个连通分量缩为一个节点，这也是非常容易的。

然后递归调用步骤 1~3，就可以完成图连通性的判定。

不过要记住，对于每一个 v∈G'，我们还要知道其在原图 G 中是由哪些节点合并来的，并且将其还原回去，将其连通性复制到其代表的图 G 中的每个节点上。这个也是比较容易实现的。

小可：那么这个算法的复杂度如何呢？

内容来源：灯塔大数据