更快的第二好 MST 算法？

我正在为此苦苦挣扎。

我们可以使用 Kruskal 算法或 Prim 算法得到 MST。

对于“第二好的”MST，我可以：

1. 首先使用上述任一算法获取 MST。
2. 对于来自 MST 的最优边缘的每个 V-1：
   A。首先删除或标记边缘
   b.继续计算 MST，无需此操作 边缘
   C。比较并记录下“第二好的”MST 上一次迭代
3. 最终我们得到了“第二好的”MST

但这在 O(VE) 中运行，其中 V 是顶点数，E 是边数。

如何使用并查不相交集或 LCA（最低共同祖先）来提高速度？

提示、伪代码或网页链接指针。

任何帮助将不胜感激！谢谢：）

我将描述该问题的多对数解决方案。让我们介绍一些定义。我们将表示：

1. 图的顶点集V，图的边集E和 MST 边集T.
2. 顶点之间的图的边v and u by {v, u}.
3. 边重e by W(e)和 MST 的权重W(T).

我们来考虑一下功能MaxEdge(v, u)，它等于之间的简单路径上具有最大权重的边v and u属于T。如果有几条权重最大的边MaxEdge(v, u)可以等于它们中的任何一个。

为了找到第二好的MST，我们需要找到这样的边缘x = {p, q}, that:

1. x不属于T.
2. 功能W(x) - W(MaxEdge(p, q))是最小的可能。

可以证明第二好的 MST 可以通过删除来构造MaxEdge(p, q) from T然后添加x = {p, q} to T.

现在让我们构建一个能够计算的数据结构MaxEdge(p, q) in O(log|V|).

让我们为树挑选一个根T（它可以是任何顶点）。我们将调用顶点之间的简单路径中的边数v根 - 顶点的深度v，并表示它Depth(v)。我们可以计算Depth(v)对于所有顶点O(|V|) by 深度优先搜索 https://en.wikipedia.org/wiki/Depth-first_search.

让我们计算两个函数，这将帮助我们计算MaxEdge(p, q):

1. Parent(v, i)，它等于作为顶点的父级（可能是非直接父级）的顶点v深度等于Depth(v) - 2^i.
2. MaxParentEdge(v, i)，等于MaxEdge(v, Parent(v, i)).

它们都可以通过递归函数来计算，并记忆在O(|V|log|V|).

// Assumes that 2^i <= Depth(v)
Vertex Parent(Vertex v, Vertex i) {
    if (i == 0) return direct_parent[v];
    if (Memorized(v, i)) return memorized_parent[v][i]; 
    memorized_parent[v][i] = Parent(Parent(v, i - 1), i - 1);
    return memorized_parent[v][i];
}

Edge MaxParentEdge(Vertex v, Vertex i) {
    if (i == 0) return Edge(v, direct_parent[v]);
    if (Memorized(v, i)) return memorized_parent_edge[v][i]; 
    Edge e1 = MaxParentEdge(v, i - 1);
    Edge e2 = MaxParentEdge(Parent(v, i - 1), i - 1);
    if (W(e1) > W(e2)) {
        memorized_parent_edge[v][i] = e1;
    } else {
        memorized_parent_edge[v][i] = e2;
    }
    return memorized_parent_edge[v][i];
}

在我们准备好计算之前MaxEdge(p, q)，让我们介绍一下最终的定义。Lca(v, u)将表示最低共同祖先 https://en.wikipedia.org/wiki/Lowest_common_ancestor顶点数v and u在有根的树上T。有许多众所周知的数据结构可以进行计算Lca(v, u)查询于O(log|V|)甚至在O(1)（您可以在以下位置找到文章列表维基百科 https://en.wikipedia.org/wiki/Lowest_common_ancestor).

计算MaxEdge(p, q)我们将在之间划分路径p and q分为两部分：从p to Lca(p, q), from Lca(p, q) to q。这些部分中的每一个看起来都像是从顶点到其某些父级的路径，因此我们可以使用我们的Parent(v, i) and MaxParentEdge(v, i)计算函数MaxEdge对于这些部分。

Edge MaxEdge(Vertex p, Vertex q) {
    Vertex mid = Lca(p, q);
    if (p == mid || q == mid) {
       if (q == mid) return QuickMaxEdge(p, mid);
       return QuickMaxEdge(q, mid);
    }
    // p != mid and q != mid
    Edge e1 = QuickMaxEdge(p, mid);
    Edge e2 = QuickMaxEdge(q, mid);
    if (W(e1) > W(e2)) return e1;
    return e2;
}

Edge QuickMaxEdge(Vertex v, Vertex parent_v) {
    Edge maxe = direct_parent[v];
    string binary = BinaryRepresentation(Depth(v) - Depth(parent_v));
    for (int i = 0; i < binary.size(); ++i) {
        if (binary[i] == '1') {
            Edge e = MaxParentEdge(v, i);
            if (W(e) > W(maxe)) maxe = e;
            v = Parent(v, i);
        }
    }
    return maxe;
}

基本功能QuickMaxEdge(v, parent_v)跳跃长度2^i覆盖之间的距离parent_v and v。在跳跃过程中，它使用预先计算的值MaxParentEdge(v, i)更新答案。

考虑到MaxParentEdge(v, i) and Parent(v, i)是预先计算的，MaxEdge(p, q)工作于O(log|V|)，这导致我们O(|E|log|V|)解决最初的问题。我们只需要迭代所有不属于的边T并计算W(e) - MaxEdge(p, q)对于他们每个人来说。