第二分鐘成本生成樹

我正在寫一個算法來找到第二分鐘生成樹。我的想法如下：第二分鐘成本生成樹

使用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

第二分鐘成本生成樹

回答

相關問題