断开图中的所有顶点
我正在寻找一种算法，通过从图中删除该子集（以及连接这些顶点的边）的所有其他顶点变为不连接（即图不会有任何边），找到最小的顶点子集。
我有一个图论的基本知识，请原谅任何不正确。
IIUC，这是经典的最小顶点覆盖问题，不幸的是，NP完成。
幸运的是，最直观，最贪婪的算法就像在这种情况下一样好。
贪婪算法是顶点覆盖的2-近似，理论上，在独特游戏猜想下，它是尽可能好的。 在实践中，将顶点覆盖度的解决方案作为整数程序来解决，很可能会产生更好的结果。 该计划是
min sum_{v in V} x(v)
s.t.
forall {u, v} in E, x(u) + x(v) >= 1
forall v in V, x(v) in {0, 1}.
试试这种方式：
现在重新排列堆的顶点数量，然后重复上一步，直到第一个顶点相邻列表的长度为0;
Heap Q
int count = 0
while(1){
Q = Create_Heap(G)
Vertex first = Q.pop
if(first.adjacents.size() == 0) {
break
}
for( Vertex v : first.adjacent ){
RemoveEdge(first, v)
RemoveEdge(v, first) /* depends on the implementation */
}
count = count + 1
}
return count