移除最小数量的顶点以使所有顶点处于隔离状态

Question

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

{V, E}：分别表示顶点数和边数。

{A - B}：指定边的顶点对

示例输入：

4 2
1-2
3-4

示例输出：2 (这是为了隔离顶点而需要移除的最小顶点数)

约束条件：

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

Answer 1

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

这里的问题是Vertex cover问题，它是NP难的。

作为一个快速反例，请考虑取自here的图表

​

​

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

Answer 2

我将从以下DS开始：

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

然后继续将所有的键保持在一个最大堆中(其中键是NumberOfNeighbors)。

你的算法应该是这样的：

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.