algorithm - 更快的次优 MST 算法？

Question

我正在为此苦苦挣扎。

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

对于“次优”MST，我可以:

1. 首先使用上述任一算法获得MST。
2. 对于来自 MST 的最优边的每个 V-1:
   A。首先删除或标记边缘
   b.没有那个继续计算MST边缘
   C。比较并记录下“第二好的”MST上一次迭代
3. 最后我们有“第二好的”MST

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

如何使用 Union-find disjoint set 或 LCA(lowest common ancester)来提高速度？

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

任何帮助将不胜感激!谢谢:)

Answer 1

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

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

让我们考虑函数 MaxEdge(v, u)，它等于 v 和 u 之间的简单路径上权重最大的边code> 属于 T。如果有几条最大权重的边 MaxEdge(v, u) 可以等于其中任何一条。

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

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

可以通过从 T 中删除 MaxEdge(p, q) 然后添加 x = {p, q} 到 T。

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

让我们为树 T 选择一个根(它可以是任何顶点)。我们将顶点 v 和根之间的简单路径中的边数称为顶点 v 的深度，并将其表示为 Depth(v)。我们可以通过 depth first search 为 O(|V|) 中的所有顶点计算 Depth(v) .

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

1. Parent(v, i)，等于顶点 v 的父顶点(可能是非直接父顶点)，深度等于 深度(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) 将表示 lowest common ancestor根树 T 中的顶点 v 和 u。有许多众所周知的数据结构允许在 O(log|V|) 甚至 O( 1)(您可以在 Wikipedia 找到文章列表)。

为了计算MaxEdge(p, q)，我们将p和q之间的路径分成两部分:从p 到Lca(p, q)，从Lca(p, q)到q。这些部分中的每一个看起来都像是从一个顶点到它的一些父节点的路径，因此我们可以使用我们的 Parent(v, i) 和 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 和 v< 之间的距离。在跳跃过程中，它使用 MaxParentEdge(v, i) 的预计算值来更新答案。

考虑到 MaxParentEdge(v, i) 和 Parent(v, i) 是预先计算的，MaxEdge(p, q) 在O(log|V|)，这使我们得到了初始问题的 O(|E|log|V|) 解决方案。我们只需要遍历所有不属于 T 的边并为它们中的每一个计算 W(e) - MaxEdge(p, q)。