algorithm - 一个节点消失时如何组织 MST？

Question

我正在研究并提出一个问题：

我有一个最小生成树（prim算法），现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树以保持最优性？

我在这里寻找一些建议，我将感谢您的帮助。

谢谢！

Answer 1

这个问题已经得到了很好的研究。^{2001 年完成的研究找到了一种维护图形数据结构的方法，以便您可以插入或删除一条边并在 O(log 4} n)时间内更新最小生成树，据我所知，这是任何人的最佳时间限制到目前为止已经能够想出。描述这个算法的论文是密集而棘手的，但如果你有兴趣，你可以在这里找到它：

用于连通性、最小生成树、2 边和双连通性的多对数确定性全动态算法

希望这可以帮助！

Answer 2

当您删除树中的一个节点时，它可能会将图形划分为多个不连接的组件。在最坏的情况下，想象一个 MST，其中所有边缘都从一个中心节点到所有其他节点——就像一颗星星。在这种情况下，如果中心节点被移除，整个 MST 将不得不重做。所以，我想简短的答案是 - 这取决于删除了哪个节点。解决方案是像上面提到的 aix 那样做 - 找到所有由于删除节点而断开连接的组件并贪婪地连接它们。这可以从 0（如果叶节点被移除）延伸到 n-1（如果星的中心被移除）

Answer 3

如果被删除的顶点是 MST 的一个叶子，你不需要做任何事情：你仍然有一个生成树并且它仍然是最优的。

如果它不是叶子，那么您现在有两个子树。您需要做的就是通过两个子树之间存在的最短边重新连接它们。找到该边缘的最佳方法可能是使用您用于 Prim 算法的任何数据结构（或者，通过考虑所有顶点对，在 O(n^2) 中）。