更快的第二好的MST算法？

Question

我正在努力解决这个问题.

我们可以使用Kruskal算法或Prim的MST算法获得MST.

对于"次佳"MST,我可以:

1. 首先使用上述任一算法获取MST.
2. 对于来自MST的最佳边缘的每个V-1:
   a.首先删除或标记边缘
   b.继续计算没有边缘
   c的MST .比较并记录上次迭代的"次佳"MST
3. 最后我们有"第二好"的MST

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

如何使用Union-find不相交集或LCA(最低共同的ancester)来加快速度？

提示,pseodo代码或Web链接指针.

任何帮助将非常感谢!谢谢:)

Answer 1

令V为顶点集，E为边集。

让T为使用任何标准算法获得的 MST。

令为从顶点到顶点maxEdgeInPath(u,v)的唯一路径上的最大边。Tuv

对于每个顶点，u在 T 上执行 BFS。这给出了所有x属于 的maxEdgeInPath(u,x) V-u。

(x,y)找到一条不属于T最小化的边w(x,y) - w(maxEdgeInPath(x,y))

第 2ndMST 的权重为W(T) + w(x,y) - maxEdgeInPath(x,y)

这是基于此链接中提供的算法。我不确定这是否正确，我希望有人能在这里添加证明。

复杂性：计算 1 个顶点的 BST 需要O(V+E) = O(V)如下所示E = V-1因此T 总体时间复杂度为O(V^2)