通过多个最小生成树分割无向图

Question

我想通过多个最小生成树拆分无向图。我想从一些特殊的（根）节点开始构建最小生成树，并且我知道节点之间的每个权重。

是否有解决此问题的算法？如果没有严格的方法，那么任何近似方法对我来说都是很好的。

我附上两个输出示例。如果您能帮助我，我会很高兴。谢谢。

Answer 1

可以通过创建另一个特殊节点（让我们称之为红色节点）来解决该问题。将红色节点与权重为零的每个特殊节点（初始图中的黑色节点）相连。然后从红色节点搜索MST。最后，删除红色节点和该节点上的所有对应边，这会将图拆分成几个图（相同数量的特殊节点）。