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

Question

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

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

Answer 1

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

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