[至少] 三种算法可以在线性 (O(n)) 时间内找到树中的最小顶点覆盖。我感兴趣的是对所有这些算法的修改，以便我还将获得这些最小顶点覆盖的数量。
例如，对于树 P4（具有 4 个节点的路径），MVC 的数量为 3，因为我们可以选择节点：1 和 3、2 和 4 或 2 和 3。
当然，您可以描述任何免费算法的解决方案 - 不是全部 3。我只是对所有这些算法感兴趣，但如果您有什么要补充的，请不要犹豫。
我将描述我知道的算法，以使您更容易。
1.贪心算法。
我们可以注意到，对于每条边，我们都必须包含一个节点。选择哪一个？假设我们有一条带有“正常”节点和叶子的边。选择哪个节点更好？当然不是叶子，因为另一个节点可能会帮助我们增加一个边缘。算法如下：
- 从任何不是叶子的节点开始。
- 对于每个孩子进行 DFS 调用，并在它返回时检查父节点或子节点是否被标记为顶点覆盖中的节点。如果不是，你必须选择其中之一，所以选择父母（并标记它）。
- 对于一片叶子什么都不做。
这是代码：https ://ideone.com/mV4bqg 。
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> graph[100019];
int mvc[100019];
int mvc_tree(int v)
{
mvc[v] = -1;
if(graph[v].size() == 1)
return 0;
int x = 0;
for(int i = 0; i < graph[v].size(); ++i)
if(!mvc[graph[v][i]])
{
x += mvc_tree(graph[v][i]);
if(mvc[v] < 1 && mvc[graph[v][i]] < 1)
++x,
mvc[v] = 1;
}
return x;
}
int main()
{
int t, n, a, b, i;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 1; i <= n; ++i)
graph[i].clear();
for(i = 1; i < n; ++i)
{
scanf("%d%d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
mvc[i] = 0;
}
mvc[n] = 0;
if(n < 3)
{
puts("1");
continue;
}
for(i = 1; i <= n; ++i)
if(graph[i].size() > 1)
break;
printf("%d\n", mvc_tree(i));
}
return 0;
}
2.动态规划算法。
我们也可以使用递归来解决任务。
MVC(v) = min(
1 + sum(MVC(child) for child in v.children),
v.children.size + sum(MVC(grandchild) for grandchild in v.grandchildren)
)
当我们在节点 v 时，它可以在 MVC 中也可以不在。如果是，我们将它添加到我们的结果 1（因为我们包括 v）和所有 v 的孩子的子树的子结果。另一方面，如果它不在 MVC 中，那么他的所有孩子都必须在 MVC 中，所以我们将结果添加到孩子的数量中，并为每个孩子添加他们孩子的子结果（所以 v 的孙子）。该算法是线性的，因为我们检查每个节点 2 次——检查它们的父节点和祖父节点。
3.动态规划没有2。
代替节点 v 的 2 个状态（1 - 在 MVC 中，2 - 不在 MVC 中），我们可以使 3 添加“可能在 MVC 中”。这有什么帮助？首先，我们调用 MVC(v = random node, "maybe") 因为我们不知道 v 是否应该在 MVC 中。“也许”的结果是“是”和“否”的最小结果。“是”的结果是 1+sum(MVC(child, "maybe") for child in v.children)。“no”的结果是 sum(MVC(child, "yes") for child in v.children)。我认为原因很清楚。如果没有，请在评论中询问。因此，公式为：
MVC(v, "maybe") = min(MVC(v, "yes"), MVC(v, "no"))
MVC(v, "yes") = 1 + sum(MVC(child, "maybe") for child in v.children)
MVC(v, "no") = sum(MVC(child, "yes") for child in v.children)
复杂性也是 O(n)，因为每个节点都被检查了两次——“是”和“否”。