更快的次优MST算法？ [英] Faster second-best MST algorithm?

问题描述

我挣扎与此有关。

我们可以用生成树Kruskal算法和Prim算法的MST得到的。

We can get MST using Kruskal's algorithm or Prim's algorithm for the MST.

而对于次优MST，我可以：

And for "second-best" MST, I can:

1. 在第一个GET MST使用上面提及的任何算法。
2. 对于每一个V-1从MST的最佳边缘：
   一个。首先删除或者标记边缘
   湾继续计算MST没有这种 边缘
   C。比较和记录下来的次优MST与 previous迭代
3. 在最后，我们有次优MST

1. first get MST using either of the algorithm mentioned above.
2. For each V-1 of the optimal edge from the MST:
   a. first remove or flag the edge
   b. continue calculating MST without that edge
   c. compare and record down that "second-best" MST with previous iteration
3. In the end we have "second-best" MST

但这个运行在O（VE），其中V是NUM顶点，E是边数。

But this runs in O(VE) where V is num of vertex and E is number of edges.

使用联盟找到不相交集或LCA（最低的共同祖先）？怎样才能获得加速

How can get a speed up using Union-find disjoint set or LCA(lowest common ancester) ?

提示，pseodo code或网页链接指针。

hints, pseodo code, or web links pointers.

任何帮助将是非常美联社preciated！感谢：）

Any help would be highly appreciated! Thanks:)

推荐答案

让 V 是顶点集和电子是边集。

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

Let T be the MST obtained using any of the standard algorithms.

让 maxEdgeInPath（U，V）在 T的唯一路径上的最大优势从顶点 U 顶点 v 。

对于每个顶点 U T上进行BFS这让maxEdgeInPath（U，X）的所有 X 属于以武。

For each vertex u perform BFS on T. This gives maxEdgeInPath(u,x) for all x belonging to V-u.

查找边缘（X，Y）这不属于 T ，最大限度地减少 W（X，Y） - W（maxEdgeInPath（X，Y））

Find an edge (x,y) which does not belong to T that minimizes w(x,y) - w(maxEdgeInPath(x,y))

2ndMST重量为 W（T）+ W（X，Y） - maxEdgeInPath（X，Y）

Weight of 2ndMST is W(T) + w(x,y) - maxEdgeInPath(x,y)

这是根据在此链路的所提供的算法。我不知道这是否是正确的，我希望有人会在这里添加一个证明。

This is based on the algorithm provided in this link. I'm not sure if this is correct and I hope someone would add a proof here.

Compexity： 为了计算BST 1顶点需要 O（V + E）= O（V）为 E = V-1 在 T 因此，总的时间复杂度为 0（V ^ 2）

Compexity: To compute BST for 1 vertex takes O(V+E) = O(V) as E = V-1 in T Hence overall time complexity is O(V^2)

这篇关于更快的次优MST算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！