algorithm - 克鲁斯卡尔的算法 : Update MST when an edge becomes mandatory

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 在同一个集合中，找到部分 MST 中已经存在的最大加权边使得与 (u, v) 的循环并将该信息存储在矩阵 M 中的 M[u][v] 中。这样做，当边成为强制性时更新 MST 的问题将在 O(1) 中得到解决。

谁能帮我解决这个问题？

Answer 1

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

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

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