algorithm - 动态最小生成树

Question

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

Answer 1

O(n log n)使用克鲁斯卡尔算法。关键思想是原始 MST 中未使用的任何边也不会在新 MST 中使用。所以只需对n新边O(n log n)进行排序，将这个排序列表与旧 MST 的边列表合并（你保持排序顺序，对吗？）O(n)，然后在生成的边排序列表上重新运行 Kruskal 算法O(n)-ish。