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

Question

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

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

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

PS 我知道这个问题与语言无关，但我使用 C++ 和 STL 进行编码。

score 1 · Accepted Answer

如果每个节点 i 只有布尔标签（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

label(v)=true 的节点 v 是一个最大独立集。它们是独立的，因为根据构造，任何带标签的节点 v 都不能有带标签的邻居。它们是一个最大集合，因为您只是激活标签，并且如果另一个已标记的邻居 w 阻止了节点 v，则只会留下未标记的节点。

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

score 0 · Accepted Answer

我使用划痕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;
}

Now used == true 表示所有使用的顶点。如果你愿意，其他的可以折叠出来。

score 0 · Accepted Answer

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

从阅读您所写的内容来看，似乎没有遍历图表中的节点的方法。您如何代表 DFS 等的堆栈？

3 回答 3