我遇到了这个问题-在无向图中，每个节点和边都有权重。所有权重均为非负数。给定一个值S，找到边权重最小的连接子图，以使其节点权重之和至少为S.
最明显的解决方案是考虑所有可能子图的蛮力方法。但是时间复杂度是指数级的。有没有更好的算法呢？我的直觉是，我们可以将节点权重转换为边缘权重，然后应用生成树算法。但是我无法清楚地解决它。如何解决这个问题呢？
编辑:看起来我对子图的描述还不够清楚。选定的子图必须是单个连接的组件。我希望现在很清楚。
最佳答案
我认为，通过减少Steiner树问题，可以解决此问题。给定一个图G和需要跨越的一组节点S，请将S中所有节点的权重设置为一个，将其他所有节点的权重设置为0。节点权重至少为| S |的子图。具有最小总边缘成本的树必须是树(如果有任何周期，则从周期中删除边缘只会降低成本)，并且必须连接所有需要跨越的节点。因此，这是一棵Steiner树。总的来说，这种减少可以用多项式时间来计算，因此您的问题是NP难的。
关于algorithm - 最小边权重和节点权重> = Val的子图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33838408/