如何高效确定可移除节点 保持图连通且最小化带权图总权重

问题规则重述 #

• 节点权重为-1的是快乐节点，不允许被移出；权重为正的是非快乐节点，可按需移出
• 核心约束：移出操作完成后，剩余节点必须构成连通图
• 优化目标：最小化剩余图的总权重（等价于尽可能多移出高权重的非快乐节点）
• 示例说明：如果直接移出权重为10、8、10的三个非快乐节点，剩余的快乐节点会被分割为互不连通的部分，违反约束；该场景下最优解为移出权重和10+8+5=23的节点，剩余图连通且总权重最低。
  

问题本质 #

这是典型的节点加权斯坦纳树问题，所有必须保留的快乐节点就是斯坦纳树的终端节点：我们需要选出一个覆盖所有快乐节点的连通节点子集，让这个子集的总权重尽可能小，不在子集内的非快乐节点就是可以移出的节点。
因为快乐节点的权重固定为-1，这部分的权重贡献是固定值，我们实际只需要最小化用来连通快乐节点所必须保留的非快乐节点的权重和即可，和示例的最优逻辑完全匹配。
两种边界场景可以直接出结果：

• 图中没有快乐节点：直接移出所有节点，剩余空集总权重为0，是全局最优
• 图中只有1个快乐节点：只保留这一个快乐节点，其余所有非快乐节点全部移出即可，剩余图天然连通

高效求解方案 #

根据图的规模和快乐节点的数量选择对应解法即可：

场景1：快乐节点总数k较小（通常k≤15） #

用斯坦纳树的状态压缩动态规划解法，是该场景下的精确最优解法，时间复杂度为O(n·3^k + m·2^k·logn)，其中n为总节点数，m为总边数：

1. 先给所有快乐节点编号，用二进制位mask表示当前连通的快乐节点集合
2. 定义状态dp[mask][u]：连通了mask对应的快乐节点、且包含节点u的子图的最小权重
3. 状态转移分两步：
   • 子集合并：对同一个节点u，将mask拆分为两个互补的二进制子集，合并两个子集的最优解更新当前值
   • 最短路松弛：固定mask值，用Dijkstra算法遍历更新相邻节点的dp值，模拟子图扩张连通的过程
4. 最终取dp[全1mask][*]的最小值，对应的连通子图就是需要保留的节点集合，其余非快乐节点全部移出。
   当快乐节点数为2时，这个解法退化为求两个快乐节点之间的最小节点权路径，和直觉逻辑完全一致。

场景2：图规模极大、快乐节点占比很高 #

如果快乐节点的数量接近总节点数，不需要引入太多非快乐节点就能实现连通，可以用线性时间的剪枝法：

1. 先从全量节点的连通图开始，从所有叶子节点（度为1的节点）开始遍历
2. 如果当前叶子节点是非快乐节点（权重为正），直接将其移出，同时更新相邻节点的度
3. 重复上述过程直到所有叶子节点都是快乐节点，剩下的节点就是需要保留的集合。
   这个方法在快乐节点占比高的场景下可以得到最优解，且运行速度极快，适合大规模图场景。

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