假设给定图 G 的最小生成树 T(n 顶点和 m 条边)和我们将添加到 G 的权重为 w 的新边 e = (u, v)。 给出一个有效的算法来找到图 G + e 的最小生成树。 您的算法应该在 O(n) 时间内运行才能获得全部分数。
(c) 来自 Skiena 手册
从 u 或 v 开始 Prim 或 Kruskal 算法，直到我们到达给定生成树路径的片段？似乎新的生成树不会从一条新边上发生太大变化。
最佳答案
确定G中新边的端点之间的路径。如果该路径中的最大长度边大于新边的最大长度，则将其替换为新边。这在 O(N) 时间内运行。
关于algorithm - 向图中添加新边并在 O(n) 中找到新的生成树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4809448/