算法从加权图

我试图找到第二个最好的最小生成树三位来自加权非取向图找到第二个最好的最小生成树。我知道如何使用克鲁斯卡尔算法来计算MST，我想找到第二个最好的算法，最少是这样的：算法从加权图

步骤：

排序的所有图形边缘。
计算使用的Kruskal
获得从不是在第一MST曲线图中的最小重量边缘，并将其添加到MST（现MST具有周期）
除去MST在新形成的循环中的最大重量边缘

而这应该是第二好的MST吧？

通过我所知道的方法是有指出，每个MST边缘之间运行迭代克鲁斯卡上没有选择，我只是问防雷工程边缘的图形算法的话题。

2017-04-18 Eduard Valentin

代替1-说出您'MST =（一个（a，b）= w（b，c）= 1'，并且w（c，d）=（b，c），（c，d）瓦特（d，E）= 4'。假设边“（a，c）”和“（c，e）”也存在权重w（a，c）= 4'和'w（c，e）= 5'。你的算法会添加'（a，c）'并删除其中一个加权为'1'的边，但是正确的方法是添加'（c，e）'并删除其中一个加权为'4'的边。 –

你说得对，谢谢！ –

它不工作。

步骤3之后，新添加的边缘可能成为仅包含具有非常低的成本边缘的周期的一部分，所以步骤3和4之后，MST的总成本可以显著增加。

另一方面，图形可能包含另一条边，其成本与步骤3中选择的边相同，当在MST中添加时，它将成为另一个周期的一部分，例如包含成本相对较高的边。为步骤3选择此边缘，然后应用步骤4会生成另一个生成树，优于所提议算法生成的生成树。

来源

2017-04-18 19:10:30 qwertyman

哦，我现在得到它..好像我必须检查第一个mst的所有边缘，并选择最小mst找到 –

不，你的算法是行不通的。

1  3 
/--\ 2 /--\ 
. .---. . 
\--/  \--/ 
    4  5

的MST为1,2,3- => 6.

第二最好是1,2,5- => 8.

你的算法将返回2,3,4 = > 9.

（我假设你的第4步返回的最大重量的边缘，这不是你刚才添加的一个）

这里的关键是一个1和4之间的差（3）比3和5（2）之间的差较大，所以用5个结果替换3以较低的总成本比用4.

来源

2017-04-18 19:11:11 Dukeling

算法从加权图

回答

相关问题