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

Question

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

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

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

Answer 1

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