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

Question

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

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

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

Answer 1

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