如果删除一条边，如何从旧 MST 更新 MST

Question

我是学算法的，见过这样的练习

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

如有任何帮助，我将不胜感激。

Answer 1

当你删除其中一条边时，MST 分成两部分，我们称它们为 a 和 b，所以你可以做的是遍历部分 [=] 中的所有顶点11=] 并查找所有相邻边，如果任何边在部分 a 和部分 b 之间形成 link，则您已找到新的 MST。

伪代码：

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) 复杂度，您需要具有图形的邻接表表示。

Answer 2

假设您在移除边后得到图 G'。 G' 包含两个连通分量。

让图中的每个节点都有一个componentID。根据它们所属的组件为所有节点设置 componentID。这可以用一个简单的 BFS 来完成，例如在 G' 上。这是一个 O(V) 操作，因为 G' 只有 V 个节点和 V-2 个边。

标记完所有节点后，遍历所有未使用的边并找到连接两个组件的权重最小的边（两个节点的组件ID 将不同）。这是一个 O(E) 操作。

因此总运行时间为 O(V+E)。

Answer 3

设G为嵌入最小生成树T的图；令 A 和 B 为从 T 中移除 (u,v) 后剩余的两棵树。

Premise P: Select minimum weight edge (x,y) from G - (u,v) that reconnects A and B. Then T' = A + B + (x,y) is a MST of G - (u,v).

P的证明：很明显T'是一棵树。假设它不是最小值。然后会有一个 MST - 称之为 M - 重量更小。 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。 QED

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

如果删除一条边，如何从旧 MST 更新 MST

How to update MST from the old MST if one edge is deleted

algorithm

graph-theory

graph

minimum-spanning-tree