基于BFS实现正权树maximum weight independent set 代码返回权重偏小

云上老周

2026-9-28

错误定位与修正方案

你的代码主要有4个核心错误导致返回权重偏小，逐一说明：

1. 单节点返回值错误

你在单节点的边界分支里返回的是new int[] {weights[0]}，但接口要求返回的是独立集的节点ID数组，不是权重值。这里应该返回节点ID 0，改成new int[] {0}即可，这个错误会导致单节点测试直接不通过，还可能触发数组越界。

2. 叶子节点判断逻辑错误

你用edges[i].length == 1判断叶子，但是根节点如果只有1个子节点，度也是1，会被误判为叶子，直接赋值M[0] = weights[0]、M1[0] = 0，忽略了子节点的权重，导致结果偏小。正确的判断逻辑应该是：非根节点，且子节点数量为0，或者结合BFS的深度信息判断：除根外度为1的节点才是叶子。

3. DP计算顺序错误

树的最大权独立集DP必须保证处理父节点前，所有子节点已经处理完成。你现在的逻辑是从任意叶子往上遍历，只要碰到父节点就直接标记为已处理，假如父节点有多个子节点，还没等其他子节点处理完就计算父节点的M、M1值，只累加了部分子节点的结果，权重自然偏小。
最简单的修正方式是直接用BFS遍历顺序的逆序来处理节点：BFS是按根到叶子的层次遍历，逆序就是叶子到根的顺序，处理父节点时所有子节点必然已经计算完成。

4. 结果集构造逻辑错误

你现在按节点ID从小到大遍历选节点，逻辑不严谨。正确的构造方式是从根节点开始向下遍历：

如果当前节点的父节点没被选中，且M[当前节点] > M1[当前节点]，就选中当前节点，标记它的子节点不可被选
否则不选当前节点，继续遍历它的所有子节点

核心逻辑修正示例

你可以把DP计算部分替换为以下逻辑，大幅简化复杂度：

// 拿到BFS的遍历顺序
int[] bfsOrder = bfs[1];
// 逆序遍历BFS结果，从叶子到根
for (int i = t.noOfVertices - 1; i >= 0; i--) {
    int u = bfsOrder[i];
    M[u] = weights[u];
    M1[u] = 0;
    // 遍历u的所有邻居，找到子节点（深度比u大1的就是子节点）
    for (int v : t.edges[u]) {
        if (bfs[0][v] == bfs[0][u] + 1) {
            M[u] += M1[v];
            M1[u] += Math.max(M[v], M1[v]);
        }
    }
}

结果集构造可以用BFS遍历整棵树，判断每个节点是否可选：

ArrayList<Integer> set = new ArrayList<>();
// 用一个数组标记节点是否被禁止选中（父节点被选中则当前节点禁止）
boolean[] forbidden = new boolean[t.noOfVertices];
Queue<Integer> q = new LinkedList<>();
q.add(0);
while (!q.isEmpty()) {
    int u = q.poll();
    if (!forbidden[u] && M[u] > M1[u]) {
        set.add(u);
        // 子节点全部禁止
        for (int v : t.edges[u]) {
            if (bfs[0][v] == bfs[0][u] + 1) {
                forbidden[v] = true;
                q.add(v);
            }
        }
    } else {
        // 不选u，子节点不禁止
        for (int v : t.edges[u]) {
            if (bfs[0][v] == bfs[0][u] + 1) {
                q.add(v);
            }
        }
    }
}

把原来的叶子判断、循环向上处理的逻辑全部删掉，替换成上面两段逻辑，再修正单节点的返回值，就能解决权重偏小的问题。

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