当一个节点消失时如何组织MST？
我正在做我的研究并遇到一个问题：
我有一个最小生成树（prim算法），现在我的树中的一个节点被删除，我想知道是否有一种方法可以重新组织我的树，以便最优性仍然保持吗？
我在这里寻求一些建议，非常感谢您的帮助。
谢谢你！
I'm doing my research and stuck with a question:
I am having a minimum spanning tree (prim algorithm), now one node in my tree gets deleted, I wonder if there is a way i can re-organize my tree such that the optimality still maintains?
I'm looking for some suggestions here and I will appreciate your help.
Thank you!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这个问题已经得到了很好的研究。 2001 年完成的研究找到了一种维护图数据结构的方法，以便您可以插入或删除一条边并在 O(log4 n) 时间内更新最小生成树，这是我最大的优势知识是迄今为止任何人都能想出的最好的时间限制。描述该算法的论文既密集又棘手，但如果您有兴趣，可以在这里找到它：
连通性、最小生成树、2边和双连通性的多对数确定性全动态算法
希望这有帮助！
This problem has been well-studied. Research done in 2001 found a way to maintain a graph data structure so that you can insert or remove an edge and update the minimum spanning tree in time O(log4 n), which to the best of my knowledge is the best time bound anyone has been able to come up with so far. The paper describing this algorithm is dense and tricky, but if you're interested you can find it here:
Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity
Hope this helps!
当您删除树中的一个节点时，它可能会将图划分为多个断开连接的组件。在最坏的情况下，想象一个 MST，其中所有边都从一个中心节点到所有其他节点 - 就像一颗星一样。在这种情况下，如果删除中心节点，则整个MST将不得不重做。所以，我想简短的答案是 - 这取决于删除哪个节点。解决方案是像 aix 提到的那样 - 找到所有因删除节点而断开连接的组件并贪婪地连接它们。这可以从 0（如果删除叶节点）延伸到 n-1（如果删除星形中心）
When you remove a node in the tree, it may divide the graph into more than one disconnected component. In the worst case, imagine an MST where all the edges go from one central node to all the others - like a star. In this event, if the central node is removed, the whole MST will have to be redone. So, I guess the short answer is - it depends on what node is removed. The solution is to do it like aix mentioned - find all the components which are disconnected because of the removed node and connect them greedily. This could stretch from 0 (if a leaf node is removed) to n-1 (if the center of a star is removed)
如果删除的顶点是 MST 的叶子，则无需执行任何操作：您仍然拥有生成树并且它仍然是最佳的。
如果它不是一片叶子，那么你现在就有两棵子树。您所需要做的就是通过两个子树之间存在的最短边重新连接它们。找到该边的最佳方法可能是使用用于 Prim 算法的任何数据结构（或者，简单地说，通过考虑所有顶点对，在 O(n^2) 中）。
If the deleted vertex was a leaf of the MST, you don't need to do anything: you still have a spanning tree and it's still optimal.
If it wasn't a leaf, you now have two sub-trees. All you need to do is reconnect them by the shortest edge that exists between the two sub-trees. The best way to find that edge is probably by using whatever data structure you used for the Prim's algorithm (or, trivially, in O(n^2) by considering all pairs of vertices).