我正在努力解决这个问题... 下面提到的是一种算法..我想通了..
输入图表 选择与所有其他节点匹配度最高的顶点。 删除与该节点相关的边。 将选定的顶点及其边添加到集合 X。 返回X
其中 X 返回顶点覆盖所需的最小顶点集。这种方式正确吗...？ 谢谢
最佳答案
选择度数最高的顶点并不能保证给出最佳解。例如， 你有一棵有 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)，因此我们可以说它是一个线性解。
关于algorithm - 给出一种有效的贪心算法，可以在线性时间内找到树的最佳顶点覆盖，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26985485/