如何修正无环图最小vertex cover求解代码的备忘录索引错误

原代码核心问题分析 #

1. Memo索引逻辑错误：用递变的i作为memo数组的索引完全不合理，不同节点会复用同一个数组位置，导致缓存的结果完全混乱，无法正确存储每个节点的计算状态。
2. 叶子节点处理错误：出度为0的叶子节点没有边需要覆盖，最小顶点覆盖大小应为0，而非原代码中的1。
3. DP逻辑偏离正确规则：原代码的x、y计算完全不符合最小顶点覆盖的两种核心情况，子节点的结果没有正确累加，无法得到正确的最小规模。

正确实现方案 #

针对有根无环图（树结构）的最小顶点覆盖，我们采用动态规划（DP）的方式，为每个节点维护两种状态：

• dp[node][0]：不选择当前节点时，以该节点为根的子树的最小顶点覆盖大小（此时所有子节点必须被选择，才能覆盖当前节点与子节点的边）
• dp[node][1]：选择当前节点时，以该节点为根的子树的最小顶点覆盖大小（此时子节点可选可不选，取每个子节点的最小状态值之和加1）

我们用HashMap存储每个节点的状态（方便后续回溯恢复顶点覆盖子集），而非数组索引的方式。

修正后的代码 #

import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 假设DirectedGraphNode的定义如下：
// class DirectedGraphNode {
//     private List<DirectedGraphNode> outgoingNodes;
//     public List<DirectedGraphNode> getOutgoingNodes() { return outgoingNodes; }
//     public int getOutDegree() { return outgoingNodes.size(); }
// }

public class VertexCoverSolver {
    // 存储每个节点的两种状态：key为节点，value数组的[0]是不选节点的最小大小，[1]是选节点的最小大小
    private Map<DirectedGraphNode, int[]> memo = new HashMap<>();

    public int vCover(DirectedGraphNode root) {
        if (root == null) return 0;
        dfs(root);
        // 根节点的最小顶点覆盖是两种状态的最小值
        return Math.min(memo.get(root)[0], memo.get(root)[1]);
    }

    private void dfs(DirectedGraphNode node) {
        if (memo.containsKey(node)) return; // 已计算过，直接返回

        List<DirectedGraphNode> children = node.getOutgoingNodes();
        int notSelect = 0; // 不选当前节点的情况
        int select = 1;     // 选当前节点的情况（先加当前节点的1）

        if (children.isEmpty()) {
            // 叶子节点：不选的话大小0，选的话大小1
            memo.put(node, new int[]{0, 1});
            return;
        }

        for (DirectedGraphNode child : children) {
            dfs(child); // 先递归计算子节点的状态
            int[] childState = memo.get(child);
            
            // 不选当前节点：所有子节点必须选，累加子节点选的状态值
            notSelect += childState[1];
            // 选当前节点：子节点可选可不选，累加子节点的最小状态值
            select += Math.min(childState[0], childState[1]);
        }

        memo.put(node, new int[]{notSelect, select});
    }

    // 额外：根据memo恢复顶点覆盖子集
    public void recoverVertexCover(DirectedGraphNode root, List<DirectedGraphNode> result) {
        if (root == null) return;
        int[] state = memo.get(root);
        if (state[0] < state[1]) {
            // 不选当前节点，必须选所有子节点
            for (DirectedGraphNode child : root.getOutgoingNodes()) {
                result.add(child);
                recoverVertexCover(child, result);
            }
        } else {
            // 选当前节点，子节点取最小状态对应的选择
            result.add(root);
            for (DirectedGraphNode child : root.getOutgoingNodes()) {
                int[] childState = memo.get(child);
                if (childState[0] < childState[1]) {
                    recoverVertexCover(child, result);
                } else {
                    result.add(child);
                    recoverVertexCover(child, result);
                }
            }
        }
    }
}

代码说明 #

1. Memo结构：用HashMap<DirectedGraphNode, int[]>存储每个节点的两种状态，确保每个节点的结果唯一存储，不会被覆盖。
2. DFS递归逻辑：
   • 叶子节点直接返回状态：不选则0，选则1。
   • 非叶子节点递归计算所有子节点的状态，再分别计算自身的两种状态值。
3. 子集恢复：通过回溯每个节点的状态选择，决定是否将节点加入结果集：
   • 若不选当前节点，必须将所有子节点加入结果。
   • 若选当前节点，根据子节点的最小状态决定是否加入子节点。

内容的提问来源于stack exchange，提问作者ABC123