algorithm - 修改边更新最小生成树

Question

具有 MST 的图(正权重边)如果某条边 e 被修改为新值，那么在不完全重新制作 MST 的情况下更新 MST 的最佳方法是什么。我认为这可以在线性时间内完成。此外，似乎我需要一种不同的算法，基于 1) e 是否已经是 MST 的一部分以及 2) 新边 e 是否大于或小于原始边

Answer 1

有4种情况:

1. Edge 在 MST 中并且您降低了 edge 的值:
   现在的MST还是MST

2. Edge 不在 MST 中并且您降低了 edge 的值:
   将这条边添加到 MST。现在你正好有 1 个周期。
   基于cycle property在 MST 中，您需要查找并删除该循环中具有最高值的边。您可以使用 dfs 或 bfs 来完成。复杂度 O(n)。

3. Edge 在 MST 中并且您增加其 edge 的值:
   从 MST 中删除这条边。现在您有 2 个应该连接的连接组件。您可以在 O(n) 中计算两个组件(bfs 或 dfs)。您需要找到连接这些组件的具有最小值的边。按边的值升序迭代边。复杂度 O(n)。

4. Edge 不在 MST 中并且您增加其 edge 的值:
   现在的MST还是MST