添加新顶点后更新最小生成树

Question

假设图G具有已经计算的最小生成树。如果我们向G添加新的顶点和入射边，我们如何快速更新最小树。

我最初的解决方案是选择权重最小的新添加边，然后将此边添加到已计算的树中。但似乎这种解决方案是错误的。有人可以给我一些关于这个问题的提示吗？谢谢

Answer 1

添加最小权重边缘将产生错误的结果，因为现在您有额外的边缘，并且它们中的多个边缘可以是新MST的一部分。例如，请参见图片。

您可以使用Prim的算法。在运行算法时，请考虑先前的MST边缘和新边缘。这将起作用，因为如果你在整个新图上运行Prims，那么它将添加的所有边将来自旧的MST或新边。 考虑到上述边缘，您可以使用任何其他MST查找算法以及Kruskal。