本文介绍了其次最小代价生成树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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.

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

10-11 22:17