移除最小数量的顶点，使所有顶点隔离

Question

我有一个无向连通图，我想通过移除顶点而不是边来隔离它的所有顶点，我想保持我移除的顶点数量最小。我知道要实现这一点，我必须每次移除程度最高的顶点，直到图断开。但是我需要为它写一个Java的程序，我不知道如何跟踪程度最高的顶点以及使用哪种数据结构。我得到了以下输入。

{V， E}：分别表示顶点和边的数量。
{A-B}：指定边的顶点对

样本输入：

4 2
1-2
3-4

示例输出：2（这是需要删除的最小数量的顶点，使顶点隔离）

限制条件：

1 <= V <= 10^5
1 <= E <= 3 * 10^5

Answer 1

我将从以下DS开始：

class Node
{
    int ID;
    int NumberOfNeighbors;
    List<int> NeighborIDs;
}

然后继续将所有节点保持在最大堆中（其中键是numberofneighborients）。

你的算法应该是这样的：

int numberOfDeletedNodes = 0;

While (!heap.Empty)
{
    node = heap.PopTop();
    foreach (int ID in node.NeighborIDs)
    {
        tempNode = heap.Extract(ID);
        tempNode.NumberOfNeighbors--;
        tempNode.NeighborIDs.Remove(node.ID);
        if (tempNode.NumberOfNeighbors != 0)
            heap.Insert(tempNode);
    }

    numberOfDeletedNodes++;   
}

我可能错过了一些终结案例什么的，但总的想法是删除邻居最多的节点，照顾所有的邻居*，并继续进行，直到堆是空的。

* Important: if the neighbors has no more neighbors of its own, it doesn't go back in.

Answer 2

我支持贪婪算法在这里并不总是最优的观点，即使任务是隔离顶点，而不是断开图。

这里的问题是顶点覆盖问题，它是NP-hard。

对于一个快速的反例，请考虑从这里获取的此图：

贪婪算法将从根开始，但这将需要4个顶点而不是最佳3个。