Kruskal 算法：当边成为强制性时更新 MST

Question

给定一个无向图G = (V, E)。首先询问 MST 的成本是多少。我可以很容易地找到使用 Kruskall 算法，像这样：

G = (V, E)
for each edge (u, v) in E sorted by wight
{
    if(Find(u) != Find(v))
    {
        Add (u, v) to the MST
        Union(u, v); // put u and v in the same set
    }
}

之后，对于初始图中的每条边，询问新 MST 的成本是多少，因为该边应出现在最小生成树中。

如果边缘已经存在于 MST 中，则答案保持不变。否则，我可以再次运行 Kruskall。伪代码如下：

G = (V, E)
G1 = runKruskall(G)

for each edge (u, v) in E
{
    ClearUnionSets()
    if (u, v) in G1
    {
        print costOf(G1)
    } else {
        Union(u, v)
        G2 = runKruskall(G)
        print costOf(G2)
    }
}

该方法的问题在于总复杂度为：O(E*E)

我的问题是是否存在更新上述 MST 的更好解决方案。

我在想的是，当运行第一次Kruskall时，对于每条边（u，v），如果u和v在同一个集合中，已经找到最大加权边存在于与 (u, v) 形成循环的部分 MST 中，并将该信息存储在矩阵 M 中的 M[u][v] 中。这样做，当边缘成为强制性时更新 MST 的问题将在 O(1) 中解决。

谁能帮我解决这个问题？

Answer 1

对于每条不在 MST 上的边 u-v，包含该边的最小生成树是 u-v 替换 MST 上从 u 到 v 的路径上的最大边的生成树。

要替换的边可以通过以下方式高效地找到。首先，将 MST 植根于任意顶点。我们将修改算法以找到 lowest common ancestor (LCA) of two vertices, described here。除了为每个顶点存储第 2^i 个父节点之外，我们还将存储到第 2^i 个父节点的路径上的最大边。使用此数组，在计算 LCA 的同时，我们还将计算 LCA 路径上的最大边，这为我们提供了两个顶点之间路径上的最大边。

预处理涉及在 O(E log E) 中找到 MST 并在 O(N log N) 中为 LCA 构建父 table，要求 O(N log N) space.在此之后，为每条边找到修改后的 MST 只需要对 LCA 进行一次评估，这可以在 O(log N) 中执行。因此总复杂度仅为 O(E log E).

Kruskal 算法：当边成为强制性时更新 MST

Kruskal's Algorithm: Update MST when an edge becomes mandatory

algorithm

computer-science

graph-algorithm

kruskals-algorithm