如果删除一条边，如何从旧的最小生成树更新最小生成树。

Question

我正在学习算法，看到了这样的一个练习题

我可以用指数时间来解决这个问题，但是我不知道如何证明它可以在线性时间O(E+V)内解决

非常感谢任何帮助。

- Crane

---

可能是更新边缘修改的最小生成树的重复问题。 - n. m.

Answer 1

让G成为嵌入最小生成树T的图形；在从T中删除(u,v)后，让A和B成为剩余的两棵树。

前提P：从G - (u,v)中选择连接A和B的最小权重边(x,y)。然后T' = A + B + (x,y)是G - (u,v)的MST。

P的证明：显然T'是一棵树。假设它不是最小的。那么就会有一棵更小的MST - 称之为M。它要么包含(x,y)，要么不包含。

如果M包含(x,y)，那么它必须具有形式A' + B' + (x,y)，其中A'和B'是跨越与A和B相同的顶点的最小权重树。这些不能比A和B的权重小，否则T将不是MST。所以M毕竟不比T'小，这是一个矛盾；M不存在。

如果M不包含(x,y)，那么M中存在从x到y的某条路径P。P的一个或多个边从A中的一个顶点传递到B中的另一个顶点。称这样的边为c。现在，c的权重至少等于(x,y)的权重，否则我们会选择它而不是(x,y)来形成T'。注意P+(x,y)是一个循环。因此，M - c + (x,y)也是一棵生成树。如果c的权重大于(x,y)，那么这棵新树将比M的权重更小。这与M是MST的假设相矛盾。再次说明M不存在。

由于在任何情况下，M都不存在，所以T'必须是MST。证毕。

算法：遍历A并将所有顶点标记为红色。同样地，将B的顶点标记为蓝色。现在遍历G - (u,v)的边缘列表，找到连接红色顶点和蓝色顶点的最小权重边。新的MST就是这条边加上A和B。

- Gene

---

很好的解释，但我有一个问题，为什么说“A'和B'分别与A和B跨越相同的顶点”，而不是只说“A'和B'跨越与A和B相同的顶点”？ - patpat

@soulomoon 没错，谢谢。问题已解决。 - Gene

Answer 2

当您删除其中一条边时，最小生成树会分为两部分，我们称其为a和b，因此您可以遍历来自部分a的所有顶点，并查找所有相邻的边，如果任何一条边形成了部分a和部分b之间的链接，则找到了新的最小生成树。

伪代码：

for(all vertices in part a){
    u = current vertex;
    for(all adjacent edges of u){
        v = adjacent vertex of u for the current edge
        if(u and v belong to different part of the MST) found new MST;
    }
}

复杂度为 O(V + E)

注意：您可以使用简单的数组来检查顶点是否在 MST 的部分 a 或部分 b 中。

另外请注意，为了获得 O(V + E) 的复杂度，您需要使用图的邻接表表示。

- uSeemSurprised

Answer 3

假设你在删除边之后得到了一个图G'。G'由两个连通分量组成。

让图中的每个节点都有一个组件ID。根据它们所属的组件，为所有节点设置componentID。例如，在G'上进行简单的BFS可以完成此操作。这是一个O（V）操作，因为G'仅具有V个节点和V-2条边。

一旦所有节点都被标记，就可以遍历所有未使用的边，并找到连接两个组件（两个节点的componentIDs将不同）的最小权重。这是一个O（E）操作。

因此，总运行时间为O（V+E）。

- navari