找到与图的其余部分相同的顶点的最小可能子集

Question

我必须编写一个代码，使其返回包含一组顶点的子集的大小，使得每条边在该组中至少有一个端点。这称为顶点覆盖，我的代码必须返回最小顶点覆盖。

输入：图的根（不会是循环的） 输出：最小顶点覆盖的大小。

为此，我的 vCover 调用 vCoverHelper 方法并传入图的根，即我将用于存储该特定节点的最小顶点覆盖的一维数组，以及索引的 i（最初设置为零）一维数组。这就是辅助方法的样子：

   private int vCoverHelper(DirectedGraphNode root, int[] memo, int i) {
        if (memo[i] != 0) {
            return memo[i];
        }
        if (root.getOutDegree() == 0) {
            memo[i] = 1;
            return 1;
        }
        else{
            List<DirectedGraphNode> children = root.getOutgoingNodes();

            int numChild = root.getOutDegree();
            while(numChild != 0) {
                if(i != 0){
                    int x = 1 + vCoverHelper((DirectedGraphNode) children.get(numChild - 1), memo, i - 1)
                            + children.get(numChild - 1).getOutDegree();
                    int y = vCoverHelper((DirectedGraphNode) children.get(numChild - 1), memo, i - 1)
                            + root.getOutDegree();
                    memo[i] = Math.min(x, y);
                    numChild--;
                }

            }
        }
        return memo[i];
    }

基本上我想做的是特定节点的最小顶点覆盖有两种可能。第一种情况是当前节点包含在顶点覆盖中，然后查看其孙子节点并将它们包含在顶点覆盖中，或者当前节点不包含在顶点覆盖中，我们将其子节点包含在顶点覆盖中。

我的代码返回错误的答案，我认为原因是它没有正确地将当前的最小顶点覆盖存储在数组中

memo

。我认为存在一个问题，尤其是索引

i

。它没有正确更新我。我该如何修复此代码？

我需要

memo

数组的原因是，在此之后，我希望能够编写一个单独的方法，该方法使用 memo 数组并恢复子集。

Answer 1

基本上我想做的是特定节点的最小顶点覆盖有两种可能。第一种情况是当前节点包含在顶点覆盖中，然后查看其孙子节点并将它们包含在顶点覆盖中，或者当前节点不包含在顶点覆盖中，我们将其子节点包含在顶点覆盖中。

考虑如下所示的树：

    A
   /|\
  / | \
 B  C  D
   /|\
  / | \
 E  F  G

这棵树的唯一最小顶点覆盖是{A，C} - 请花点时间说服自己这一点 - 即使 A 是 C 的父代。因此，除非您了解更多，否则您分解为两种情况是不正确的关于您的意见而不是您决定分享的内容。

---

如果你知道你的图将是一棵树——或者维基百科所说的 arborescent（“有向图，其中对于顶点 u（称为根）和任何其他顶点 v，有正是从 u 到 v 的一条有向路径”）——那么对于任何给定的顶点，有两种情况：

1. 顶点包含在封面中。它的孩子可能是也可能不是。
2. 顶点不包含在封面中。它的孩子一定是。

您可以通过计算以每个顶点为根的子树的two信息来找到线性时间内的最小覆盖：该子树的any覆盖的最小大小（称为minCoverAny[i]），以及任何此类覆盖的最小尺寸包括顶点本身（称之为minCoverWithRoot[i]）。您可以在树上的一次递归遍历中计算这些：

• minCoverWithRoot[i] 是 1 + ΣminCoverAny[j]，其中 j 范围涵盖 i
的子级
• minCoverAny[j] 是 min(minCoverWithRoot[i], ΣminCoverWithRoot[j])，同上

然后，一旦填充了这些，就可以对树进行第二次递归遍历，以找到最小覆盖范围中的实际顶点。