问题描述
我在写一个算法寻找第二个最小代价生成树。我的想法如下：
I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows:
- 使用kruskals找到最低的MST。
- 删除MST成本最低的优势。
- 在整个图形上再次运行kruskals。
- 返回新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.
这篇关于其次最小代价生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！