一棵树的最小顶点覆盖数

至少有三种算法可以在线性（O（n））时间中找到树中的最小顶点覆盖。我感兴趣的是对所有这些算法的修改，以便我还将获得这些最小顶点覆盖的数量。

例如，对于树P4（具有4个节点的路径），MVC的数量为3，因为我们可以选择以下节点：1和3、2和4或2和3。

当然，您可以描述任何免费算法的解决方案-并非全部3.我只是对所有这些算法感兴趣，但是如果您有任何要添加的内容，请不要犹豫。

我将介绍我所知道的使您更轻松的算法。

1.贪婪算法。

我们可以注意到，对于每个边缘，我们都必须包括一个节点。选择哪一个？假设我们有一个带有“普通”节点和叶子的边。哪个节点更好选择？当然不是叶子，因为另一个节点可能会帮助我们进一步提高优势。算法如下：

1. 从不是叶的任何节点开始。
2. 对于每个子对象，请进行DFS调用，并在返回时检查是否将父对象或子对象标记为顶点覆盖中的节点。如果不是，则必须选择其中之一，因此选择父项（并标记）。
3. 一片叶子什么都不做。

这是代码：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中，也可以不在MVC中。如果是，则将其添加到结果1中（因为我们包括v），并且将其添加到所有v的子级的子树的子结果中。另一方面，如果它不在MVC中，则他的所有子代都必须在MVC中，因此我们将子代数加到结果中，并为每个子代添加子代子结果（即v的孙子代）。该算法是线性的，因为我们检查每个节点2次-分别检查其父级和祖父母。

3.动态编程2。

代替节点v的2状态（在MVC中为1-，在MVC中为2-），我们可以使3添加“也许在MVC中”。有什么帮助？首先，我们称MVC（v =随机节点，“也许”），因为我们不知道v是否应该在MVC中。“可能”的结果是来自“是”和“否”的结果的最小值。“是”的结果是1 + sum（v.children中的child的MVC（child，“ maybe”））。而“否”的结果为sum（v.children中的child的MVC（child，“ yes”））。我认为原因很清楚。如果没有，请在评论中提问。因此，公式为：

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），因为每个节点都要检查两次-“是”和“否”。