每周学点大数据 | No.33最大独立集

No.33期

最大独立集

Mr. 王：好，现在我们来谈谈最大独立集的问题。首先求解最大独立集是一个NP-hard问题，接下来要介绍的这个求解方法是一个近似算法，不是精确解，因为求解精确解的开销过大。

伪代码Algorithm GREEDYMIS：

1 I = 0

2 for 每个顶点v

do

3 if I 中没有v 的邻居then

4 将v 加入I 中

5 end if

6 end for

你来解释一下这是什么意思。

小可：这个算法太简单了，就是首先拿来一个空集，然后到所有的点的集合中去找，只要I 中还没有 v 的邻居，就把 v 放进集合中。这个算法很朴素啊！

Mr. 王：没错，这是一个非常朴素的贪心算法。在内存中求解其最大独立集非常容易，但是在外存中会存在什么问题呢？

小可：显然，由于要扫描所有的节点，所以仍然非常容易出现这些节点因存储没有规律，导致其随机地存放在不同的磁盘块中，最后以 Ω(N) 的顺序结束扫描的情况。

Mr. 王：这时我们就需要设计特殊的方法来解决，以下面的图为例进行说明。

上面图中的每一个节点都有ID。在原图中，边是没有方向的，为了能够使用时间前向方法，我们要将其转化为一个DAG，也就是为这些边都加上方向。但是有一个原则，那就是所有的边都要从ID 小的节点指向ID 大的节点。

有了DAG，我们就可以按照前面介绍的时间前向方法进行处理了。

对于这个图而言，首先我们访问序号最小的1 号节点。它的后继节点是一定不会被加入到独立集中的，2,8,4,5这几个节点是1 的后继节点，等到访问它们时，记住不要将其加入到独立集中。根据拓扑序列，现在该访问2 号节点了，但由于它是1 的后续节点，所以不将其加入到I中。

在完成了对1 和2 号节点的访问之后，我们访问3 号节点。3 号节点在访问1 号节点时没有被标注为后继节点，所以3 号节点可以被加入到I 中。注意，2 的后继节点是不受影响的，因为2 号节点并没有被加入到I 中。

当访问3 号节点时，我们要记住4,6,7,11这几个节点是不能被加入到I 中的。依此类推，直到访问了所有的节点。

小可在纸上写画了一会儿，说：对于这个图来说，好像最大独立集可以比这个大。

Mr. 王：没错。由于我们使用的是一个贪心算法，它求出的解不是最优解，但对于一个较大的图来说，这个最大独立集往往还可以接受，不是那么坏。

这是一个典型的时间前向处理问题，因为它具有时间前向的特点——每当访问一个节点时，它的父节点必然已经被访问过了，也符合拓扑排序的思想。

而且它的时间复杂度也和时间前向处理方法相一致，它在本质上也是一种时间前向处理方法，图 G = (V,E) 的最大独立集的 I/O复杂度为O(sort(|V|+|E|))。

现在我们可以解释一下在链表中求独立集的一些问题了。求解方法和求一般图的最大独立集是一样的。现在的问题是，它的复杂度如何？为什么选出来的最大独立集的节点有 N/3 个？

小可：既然使用的是时间前向方法，那么复杂度也是 O(sort(|V|+|E|))。

Mr. 王：结合链表的特点呢？

小可：嗯，链表是一种特殊的图，链表也是一棵树，所以它满足树的性质 E=V-1。这就是说，E 和 V 几乎是一样大的。所以应该是 O(sort(N))。

Mr. 王：没错。至于最大独立集至少有N/3 个节点，是因为在链表中，我们每选择一个节点，就会放弃其相邻的两个节点。这也是比较容易想到的结论。

下期精彩预告：

经过学习，我们掌握了一个求解最大独立集问题的近似算法——贪心算法，通过将序列转化为一个DAG，再用时间前向方法进行处理。在下一期中，我们将讨论一种常用于磁盘上存储的图的思想，叫做缩图法，这种方法可以把图变小，使之能被放进内存中。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！

内容来源：灯塔大数据