其次最小代价生成树 [英] Second min cost spanning tree

问题描述

我在写一个算法寻找第二个最小代价生成树。我的想法如下：

I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows:

1. 使用kruskals找到最低的MST。
2. 删除MST成本最低的优势。
3. 在整个图形上再次运行kruskals。
4. 返回新MST。

我的问题是：将这项工作？有没有更好的办法也许是为了做到这一点？

My question is: Will this work? Is there a better way perhaps to do this?

推荐答案

您可以做到这一点为O（V ² ）。首先使用 Prim算法计算MST（可以在O完成（V ² ） ）。

You can do it in O(V²). First compute the MST using Prim's algorithm (can be done in O(V²)).

计算最大值[U，V] =最大成本优势的（唯一的）路径从u到v的MST 的成本。可以在O完成（V ² ）。

Compute max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST. Can be done in O(V²).

查找边缘（U，V）这不是MST的一部分，最大限度地减少 ABS（最大值[U，V] - 重量（U ，V））。可以在O（E）来完成==Ø（V ² ）。

Find an edge (u, v) that's NOT part of the MST that minimizes abs(max[u, v] - weight(u, v)). Can be done in O(E) == O(V²).

返回 MST = MST - + {拥有最多[U，V]重边} {（U，V）} ，它会给你第二最好的MST。

Return MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}, which will give you the second best MST.

<一个href="http://74.125.77.132/search?q=cache%3axqm4F3DFYvMJ%3awww.swen.uwaterloo.ca/~jlian/courseMaterial/ece250/tutorial-7.ppt+second+best+mst&cd=7&hl=en&ct=clnk">Here's链接以伪code和更详细的解释。

Here's a link to pseudocode and more detailed explanations.

这篇关于其次最小代价生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！