动态最小生成树

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。