algorithm - 给出一个高效的贪心算法，在线性时间内找到一棵树的最优顶点覆盖

Question

我正在努力解决这个问题......下面提到的是一种算法......我想出了......

输入一个图，选择一个与所有其他节点匹配度最高的顶点。移除在该节点上发生的边。将选定的顶点及其边添加到集合 X。返回 X

X 返回顶点覆盖所需的最小顶点集。这种方式是否正确......？谢谢

Answer 1

选择度数最高的顶点并不能保证给出最佳解决方案。例如，你有一棵有 7 个顶点的树，边的列表如下：

1 2 // (1,2) is connected.
1 3
1 4
2 5
3 6
4 7

最小顶点覆盖是 {2,3,4}，但是，根据您的贪心方法，您将首先选择 {1}，然后您将选择至少 3 个顶点来覆盖左侧 3 条边。

确实，有一种贪心算法可以解决树的顶点覆盖问题，就是在每一步都找到一个叶子（因为输入是一棵树，所以除非没有剩下边，否则总是可以找到这样的叶子），然后选择顶点覆盖集X的叶子的邻居。当图为空时，返回X作为最小顶点覆盖。当 E = V-1 时，复杂度为 O(E)，因此我们可以说它是一个线性解。