动态最小生成树 [英] dynamic minimum spanning tree

问题描述

我想打一个动态最小生成树。我有一个现有的MS树在n个顶点，我再加上一个顶点和边从这个新的顶点所有现有的顶点。如何更新的MST为有效的新的图形？为O（n）将是最佳的。我也可以使删除顶点运行效率？

I want to make a dynamic minimum spanning tree. I have an existing MS tree over n vertices and I add one more vertex and edges to all the existing vertices from this new vertex. How can I update the MST for the new graph efficiently? O(n) would be optimal. Can I also make delete vertex operation efficient?

推荐答案

为O（n log n）的使用Kruskal算法。关键思想是在原始的MST不使用任何边缘，不会在新的MST使用，也可以。因此，只要排序 N 新边为O（n log n）的，合并此排序列表的边缘名单老MST（你保持有序，对吧？） O（N），然后边产生的排序列表上运行Kruskal算法重新O（n）的-ish 。

O(n log n) using Kruskal's algorithm. The key idea is any edges not used in the original MST will not be used in the new MST either. So just sort the n new edges O(n log n), merge this sorted list with the list of edges of the old MST (which you kept in sorted order, right?) O(n), then run Kruskal's algorithm anew on the resulting sorted list of edges O(n)-ish.

这篇关于动态最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！