我正在尝试解决这个问题...下面提到的是一种算法。我想通了..
输入图表 选择与所有其他节点匹配程度最高的顶点。 删除此节点上入射的边。 将所选顶点及其边添加到集合 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），因此我们可以说它是一个线性解。