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

Question

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

有什么算法可以解决这个问题吗？如果没有严格的方法，任何近似的方法对我来说都可以。

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

Answer 1

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