algorithm - 添加新节点后如何找到MST？

Question

MST (Minimum Spanning Tree)添加新节点或改变路径距离后我们如何找到？

我需要帮助来解决这个问题。有谁能够帮助我？

谢谢。

Answer 1

添加新边时：

您将需要从修改/新边的一侧执行图形遍历，最简单的是 DFS。如果您可以回到以前的节点，那么您就有了一个循环。

在该循环中，您将需要删除最大的边缘。您将再次获得一棵树，它是最小跨度树。

如果要更改边权重，则需要：

• 通过临时移除新边，将图形断开为 2 个组件 A 和 B。
• 如果新边的权重比以前小，您可以将其放回原处。否则：
• 遍历您之前处理过的边，并检查它们是否将 A 连接到 B。
• 从中选择最小的边，并使用该边连接组件。

同样，您会得到一个新的最小生成树。

总的来说，这是O(V+E), 乘以逆阿克曼的一个小因数。