动态最小生成树

我想制作一个动态最小生成树。我在n个顶点上有一棵现有的MS树，我从这个新顶点向所有现有顶点添加了一个顶点和边。我如何有效地更新新图形的MST？ O（n）将是最优的。我也可以使删除顶点操作高效吗？动态最小生成树

2012-03-21 anirudh

相关 - > http://stackoverflow.com/questions/2679472/updating-a-minimum-spanning-tree-when-a-new-edge-is-inserted – digEmAll 2012-03-21 19:56:50

在这里，我正在增加树的大小并且引入n个新边缘，可能是每个边缘被替换并且仍然花费时间应该是O（n）。 – anirudh 2012-03-21 20:01:22

添加顶点时，是否始终将新顶点的边添加到* all *现有顶点？如果是这样，新的MST只是NEW-VERTEX + MST ... – digEmAll 2012-03-21 20:05:10

O(n log n)使用Kruskal算法。关键的想法是原始MST中不使用的任何边缘都不会在新的MST中使用。因此，只需对n新边缘O(n log n)进行排序，将此排序列表与旧MST的边缘列表合并（您保存在排序顺序中，对吧？）O(n)，然后在得到的排序列表O(n)-ish上重新运行Kruskal算法。

来源

2015-04-08 08:50:47 Atsby

动态最小生成树

回答

相关问题