algorithm - 给定图中的旧最小生成树，是否存在用于将新节点添加到最小生成树的 O(|V|) 算法？

Question

我知道它可以通过使用 DFS 在 O(|V| + |E|) 中更新，但是是否可以在 O(|V|) 中更新？

编辑:如果这不可能，O(|V| + |E|) 算法究竟如何工作？

Answer 1

更新图的最小生成树 (MST) 不限于将新顶点连接到现有 MST。还应该验证初始 MST 中使用的边仍然是连接所有顶点的最便宜的可能方式。在某些情况下，v_k 可能是这样一个节点，它可以彻底改变图 G 的整个现有 MST。新的顶点和随之而来的边可能形成一种更便宜的连接方式图的顶点，因此，初始 MST 中的一些(或所有)边可能变得不是最便宜的。

可以很容易地构造一个这样的案例。考虑初始图 G=(V={1,2,3}, E={(1, 2), (2, 3), (1, 3)}) 其中每条边的权重为 100。然后引入一个顶点 4，以及从 4 到彼此顶点的边，每个顶点的权重为 1。G 的初始 MST 将具有 E 的任意两个元素，但是在添加新节点之后，MST 将完全由不同的边缘。

也许一个聪明的数据结构可能会给你带来比 O(|E|) 更好的时间复杂度，但是需要检查每条边的有效性(即它们是否仍然是连接所有顶点的最便宜的方式)初始 MST 以及新添加的边意味着时间复杂度取决于 |E| 的大小。初始 MST 可以提供有用的信息，可以帮助扩展它以覆盖具有更小时间复杂度的新顶点，这是一个有效的想法。然而，MST 的定义在很大程度上依赖于图本身，并且更新图可能使所有初始 MST 失效，从而使它指示的有关图的信息变得无用。因此，虽然我没有在这里提供精确的数学证明，但我认为在将新节点(及其边)添加到图中时，不存在 O(|V|) 算法来更新 MST。