第二分钟成本生成树

我正在写一个算法来找到第二分钟生成树。我的想法如下：第二分钟成本生成树

使用kruskals找到最低的MST。
删除MST的最低成本边缘。
再次在整个图表上运行kruskals。
返回新的MST。

我的问题是：这会工作吗？有没有更好的方法来做到这一点？

2010-04-22 Evil

好吧，我有另一种想法......但我不是很确定那个作品.....在以前的避免边缘中添加最小重量到最新的Mst。如果我的想法是错误的，所有人都可以举个例子吗？ – 2011-09-12 20:57:45

考虑这种情况：

------100---- 
|   | 
A--1--B--3--C 
     |  | 
     |  3 
     |  | 
     2-----D

的MST由A-B-d-C（成本6）。第二个最小成本是A-B-C-D（成本7）。如果删除最低成本优势，您将获得A-C-B-D（成本105）。

所以你的想法不会工作。我没有更好的主意，但...

来源

2010-04-22 16:42:33

此外，如果最小边缘碰巧连接一个垂饰顶点，删除它并重新计算MST甚至不会给你一个MST。 – csprajeeth 2013-09-11 17:20:54

你可以这样做 - 尝试从图中一次一个地移除MST的边缘，然后运行MST，从中取出最小值。所以这与您的类似，除了迭代：

使用Kruskals找到MST。
对于MST每个边缘：在MST
1. 删除边从图中
2. 计算MST”
3. 跟踪的最小生成树
4. 添加边缘回绘制
退运最小的MST。

来源

2010-04-22 17:00:52 Larry

谢谢。我画出了一些例子，这个想法似乎适用于我所有的例子。 :) – Evil 2010-04-22 18:10:15

这可行 - 但它是一个广泛的搜索，将O（N^2 * logN）相比，克鲁斯卡尔的O（NlogN）复杂性。 – 2010-04-22 18:14:54

这只是一种说法，即MST和MST_2在一个边缘上有所不同 - 这里有更好的算法，但它是一种考虑它的方法。还有O（VE）算法 - Kruskal实际上是O（V log E），使得上面的O（V^2 log E）。 – Larry 2010-04-22 18:29:39

您可以在O（V ）中做到这一点。首先使用Prim's algorithm计算MST（可以在O（V ））中完成。

计算max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST。可以在O中完成（V ）。

找到边缘(u, v)这不是MST的一部分，它将abs(max[u, v] - weight(u, v))最小化。可以在O（E）== O（V ）中完成。

返回MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}，它会给你第二好的MST。

Here's a link伪代码和更详细的解释。

来源

2010-04-22 20:17:47 IVlad

这里是一个计算所述第二最小生成树为O树（N^2）

首先找出mimimum生成树（T）的算法。这将需要O（n^2）而不使用堆。
重复每个边e在T.= O（n^2）
可以说当前树的边缘是e。这棵树边缘将树分成两棵树，比如说T1和T-T1。 e=(u,v)其中u在T1中，v在T-T1中。 = O（n^2）

对于T-T1中的每个顶点v重复。 = O（N^2）

在T-T1和e所有v选择边缘e'=(u,v)”在G（原始图），它是最小
计算新形成的树的重量。比方说W=weight(T)-weight(e)+weight(e')
选择具有最小重量

来源

2011-02-26 12:38:50 opsuthar

这与拉里的回答了一个T1。

在MST

找到MST，

对于每个new_edge =不是一个边缘之后添加到new_edge MST。
找到形成的循环。
在周期中找到最大权重的边沿，而非您所添加的非MST边沿。
将重量增加记录为W_Inc = w（new_edge）-w（max_weight_edge_in_cycle）。
如果W_Inc < Min_W_Inc_Seen_So_Far然后
- Min_W_Inc_Seen_So_Far = W_Inc
- edge_to_add = new_edge
- edge_to_remove = max_weight_edge_in_cycle

从下面的链接方案。
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

来源

2011-03-07 19:50:39

您的方法不起作用，因为它可能是最小的情况。 MST中的加权边是一个桥（只有一条边连接图的两部分），因此从该集删除该边将导致2个新的MST与一个MST相比。

来源

2013-10-07 04:58:46 mridul

轻微修改您的算法。

Use kruskals to find lowest MST. 
    for all edges i of MST 
     Delete edge i of the MST. 
     Run kruskals again on the entire graph. 
     loss=cost new edge introduced - cost of edge i 
    return MST for which loss is minimum

来源

2013-11-20 22:31:10 aitrom

第二分钟成本生成树

回答

相关问题