algorithm - 求点亮二叉树最少需要打开多少个开关

Question

考虑像这样的二叉树:

将节点想象成开关，它们最初是 OFF，节点之间的边缘是管灯(最初不发光)。当我们打开特定节点时，连接到该节点的所有边缘(管灯)都会发光。找到要使整个二叉树发光需要打开 ON 的最少开关数。

例如，如果我打开 2,3,4 和 9 或 2,3,8,9，则所有灯管都会发光。所以，答案是 4 [见图表]

我在一次采访中被问到这个问题。谁能帮我解决算法/伪代码？无需工作代码。

对于程序员和编码员来说，认为输入是这样的:

n:给定的边数

然后 n 行以 x y 的形式跟随，其中 x 和 y 是边的两个端点。

根据上图，输入将是:

10
1 2
1 3
2 5
...

到目前为止，我已经弄清楚了一些情况，例如:我永远不需要照亮叶节点

是否存在基于上述事实的简单递归解决方案？

编辑:如果仅将树的 Root 作为 input 给出，算法会改变吗 [假设树表示为链接列表] ??

Answer 1

这是树上的最小顶点覆盖问题 (MVC)。您可以通过两种方式解决它:

1. 树是一个二分图，MVC 问题等价于寻找多项式时间可解的最大匹配。

2. 按照下面的贪心算法来做。任意根树。选择所有连接到叶子的顶点并将它们放入最终集合(打开它们)。 (那些顶点或叶子应该在最终解决方案中)。删除那些顶点和所有边，并保留与它们相连的顶点，然后在图的其余部分使用相同的算法。

以下是该算法有效的证明:假设输入是大小为“n”的森林。显然，叶子或其邻居应该被打开(除了它没有连接到它的边缘)。所以第一步是正确的。

一旦我们删除了叶子的所有父节点和所有叶子，剩下的图就是在“n-t”个顶点上的森林，其中 t 是原始图中叶子及其父节点的数量。假设我们知道开始时的离开节点是什么。我们执行以下操作来解决 O(n) 中的问题:

如果我们知道删除那些“t”顶点后的叶子是什么，那么我们就可以解决 T(n) = O(t) + T(n-t) 中的问题，其中结果为 T(n) = O(n)。为了在删除那些 t 顶点后找到新的叶子，我们创建了一个新的叶子列表。每次我们删除这些 t 顶点中的任何一个时，我们都会检查它们是否具有未连接到原始叶子的度数为 1 的邻居，并将该顶点添加到新的叶子列表中。在我们完成移除叶子及其邻居的过程后，我们用新的叶子列表更新原始叶子列表。所以在每个步骤中我们都有叶子列表，因此可以在 O(n) 中完成。