algorithm - 多边权重减少导致的新 MST？

Question

我们知道原始图和原始MST。现在我们改变图中的 k 个边权重。有什么方法可以在 O((n + k) log n) 时间内从旧图生成新的 MST？

Answer 1

• 从原始 MST 开始。
• 将所有权重降低的边添加到 MST。如果边缘已经在原始 MST 中，则将其保留在那里并减少边缘权重。
• 让这个新的结果图为 G。
• 在 G 上求解 MST。

MST 可以在 O(mlogn) 时间内解决，其中 m 是边数，n 是顶点数图。

因为 G 有 O(n + k) 边，你可以在 O((n+k)logn) 中找到新的 MST > 时间。