使用深度优先搜索计算最大独立集

Question

一个无向图G=(V，E)的独立集是一个子集I，其中没有任何两个顶点在I中是相邻的。也就是说，如果u和v在I中，那么(u,v)不在E中。最大独立集M是一个独立集，如果我们将任何其他顶点添加到M中，则它将不再是独立的。每个图都有一个最大独立集。(你能看到这个吗？这个问题不是练习的一部分，但值得思考。)给出一个有效的算法来计算图G的最大独立集。这种方法的运行时间是多少？

我不确定深度优先搜索的修改是否可以解决上面的问题，但这是我的尝试（注意：我不要求代码，只要求高层次的描述）。

使用DFS，我们将从某个起始顶点S1开始遍历图的所有顶点。从S1开始，如果没有相邻边存在，则我们转到相邻边S2。如果不存在相邻边，我们将S1添加到最大独立集M中，因为该顶点在G中与任何其他顶点之间没有边缘，如果是这种情况，则选择另一个顶点S1'并从该点开始进行DFS（递归）。

假设S1和S2之间有一条边，那么我们可以将S1添加到独立集中，但不能将S2添加到其中，然后DFS继续，我们添加S3，因为S3与S1没有共享的边缘，DFS继续，我们一直添加S[k]到集合M中，只要它与已存在于M中的当前元素不共享边。

这将需要O（| V | + | E |）的时间复杂度。原因：DFS是O（| V | + | E |），每次移动到新节点时，我们必须将其与M中的某些K元素进行比较，以确保它们不共享边缘。那就是O(k (| V | + | E |))= O(|V| + |E|)。

最坏情况：空图，|V|调用DFS给我们O（| V |（| V | + | E |）

问题：

(1) 这正确吗？我实际上找到了最大独立集还是最大独立集？

(2) 如果正确，这样做高效吗？

如果完全错误，我真的很感激一个解决方案，我已经思考了这个问题一段时间了。

- Mutating Algorithm

---

你给出了一个时间复杂度为O（|V| + |E|），然后是一个最坏情况下的时间复杂度为O（|V|（|V| + |E|））。这到底是哪个？或者第一个是在衡量什么？ - j_random_hacker

据我理解，一个更易于理解的方法是连通分量分析，基本上是深度优先搜索，然后从每个连通分量中选择一个单一节点；时间复杂度也将是O(|V| + |E|)。 - Codor

我们通常关注最坏情况的复杂度。此外，第一次复杂度是否真正是描述平均复杂度的准确方式并不清楚——我看不到任何阻止k与|V|成比例的东西，如果这种情况发生，那么平均情况下的复杂度也是O（|V|（|V| + |E|））。 - j_random_hacker

@piotrekg2 上述问题是NP完全问题，我相信你可以找到任何图的最大独立集，但不是最大值。 - Mutating Algorithm

@piotrekg2：在多项式时间内找到最大独立集很容易。但是找到整体最大独立集是NP难问题。 - j_random_hacker

Answer 1

这是我的解决方案：

输入：一组顶点 V，邻接列表 E[v]（每个顶点一个）：

1. 准备一个大小为 |V| 的布尔值数组 take[]。所有元素最初都设置为 false。该数组告诉我们哪些顶点已经被包含在结果中。
2. 将 take[0] 设置为 true。
3. 对于每个顶点 v = 1..|V| - 1：如果 E[v] 不包含任何边 (v, u)，使得 take[u] 是 true，则将 take[v] 设置为 true。
4. 返回所有顶点 v，使得 take[v] 是 true。

总时间复杂度为 O(|V| + |E|)。

- piotrekg2