我正在进行研究，遇到了一个问题：
我有一个最小生成树（prim算法），现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树，使得最优性仍然保持？
我在这里寻求一些建议，非常感谢您的帮助。
谢谢！
3个回答
2
这个问题已经得到了很好的研究。2001年的研究发现了一种维护图数据结构的方法，使得您可以在O(log4n)的时间内插入或删除边，并更新最小生成树，据我所知，这是目前为止任何人能够想出的最好的时间界限。描述这个算法的论文很复杂，但如果您感兴趣，可以在这里找到它：Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity。希望这可以帮到您！
- templatetypedef
1
当您从树中删除一个节点时，它可能会将图形分成多个不连通的组件。在最坏的情况下，想象一下所有边缘都从一个中心节点到其他所有节点的MST - 就像一颗星。在这种情况下，如果删除中心节点，则整个MST将不得不重新进行。所以，我想简短的答案是 - 这取决于删除哪个节点。解决方案是像aix提到的那样 - 找到由于删除节点而断开连接的所有组件，并贪婪地将它们连接起来。这可以从0（如果删除叶节点）到n-1（如果删除星的中心）延伸。
- kyun
-1
如果被删除的顶点是MST的叶子节点，你不需要做任何事情：你仍然有一棵生成树，它仍然是最优的。
如果它不是叶子节点，现在你有两个子树。你需要做的就是通过连接两个子树之间存在的最短边来重新连接它们。找到这条边的最佳方法可能是使用你用于Prim算法的任何数据结构（或者通过考虑所有顶点对，在O(n^2)时间内轻松找到）。
- NPE
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接