记忆保守的最大独立顶点集

Question

我想为无向图中设置的最大独立顶点找到一种内存保守但有效的算法。

传统算法使用辅助数据结构（原始图形的副本）来实现它。我想避免这种并行结构，因为内存分配对于实时实现来说很慢，而且我有一些内存边界。我只想用布尔标签标记 MIS 中的节点。可能吗？

请注意，我不想要最大独立集，而是最大独立集。

附言我知道这个问题与语言无关，但我正在用C++和STL编码。

Answer 1

如果你每个节点只有布尔标签（i），这是一个解决方案。需要时间 O（|V|+|E|），其中 |V|是节点数和 |E|是输入图形中的边数。

For all nodes v
   set label(v)=false;
For all nodes v
   if (all neighbors w of v have label(w)=false)
      set label(v)=true

标签（v）=true 的节点 v 是一个最大独立集合。它们是独立的，因为根据构造，任何标记的节点 v 都不能有标记的邻居。而且它们是最大集合，因为您只激活标签，并且只有在另一个已标记的邻居 w 阻止它时才保留节点 v 未标记。

优化说明：如果节点编号为 1...n，则只需检查邻居 w=1..v-1，因为任何其他 w 都不能有 label（w）=true。

Answer 2

如果不确切知道您的数据结构是什么，就很难回答此类问题。近地图操作的常用技巧是从指针中窃取两个本来为零的位，并对图结构进行可逆更改，但我不确定它们在这里如何应用。

通过阅读您编写的内容，似乎没有遍历就无法遍历图形中的节点。您如何表示DFS的堆栈？

Answer 3

我使用划痕vector或deque<bool>来指示元素、边或小平面使用的顶点......

std::deque<bool> used(vertex.size(), false);
for (size_t e = 0; e < edge.size(); ++e)
{
    used[edge[e].v1] = true;
    used[edge[e].v2] = true;
}

现在使用 == true 表示所有使用的顶点。 如果需要，可以将其他的折叠起来。