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

Question

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

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

Answer 1

添加最小权重边会给出错误的结果，因为现在您有额外的边，并且其中不止一条边可以成为 新 MST 的一部分。例如看图片。

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