我正在做我的研究并坚持一个问题:
我有一个最小生成树(prim 算法),现在我的树中的一个节点被删除了,我想知道是否有一种方法可以重新组织我的树以保持最优性?
我正在寻找一些建议,非常感谢您的帮助。
谢谢!
最佳答案
这个问题已经被很好地研究过了。 2001 年完成的研究找到了一种维护图形数据结构的方法,以便您可以插入或删除一条边并及时更新最小生成树 O(log4 n),这对我来说是最好的知识是迄今为止任何人都能够想出的最好的时间限制。描述该算法的论文内容密集且棘手,但如果您有兴趣,可以在这里找到它:
希望这对您有所帮助!
关于algorithm - 当一个节点消失时如何组织MST?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5354034/