我试图从加权无向图中求出第二次最佳最小跨越3。我知道如何使用Kruskal算法计算MST,我正在考虑这样找到第二最佳最小算法:
步骤:
这应该是第二好的MST对吧?
顺便说一下,我知道有一个主题指出了一个算法,它在每个MST边之间迭代,然后在图上运行Kruskal,而没有选择边缘,我只是在问我的算法是否有效。
发布于 2017-04-18 19:10:30
它不起作用。
在步骤3之后,新添加的边缘可能成为只包含非常低成本的边缘的循环的一部分,因此在步骤3和步骤4之后,MST的总成本会显著增加。
另一方面,该图形可能包含另一个边缘,其成本与步骤3中选择的边缘相似,当添加到MST中时,它将是另一个周期的一部分,例如,包含成本相对较高的边缘。为步骤3选择此边缘,然后应用步骤4将导致另一个生成树,比所提出的算法生成的生成树更好。
发布于 2017-04-18 19:11:11
不,你的算法不管用。
1 3
/--\ 2 /--\
. .---. .
\--/ \--/
4 5MST为1,2,3 => 6。
其次是1,2,5 => 8。
您的算法将返回2,3,4 => 9。
(我假设您的步骤4是返回最大重量边,而不是您刚才添加的那个)。
这里的关键是,1和4 (3)之间的差大于3和5 (2)之间的差,所以用5代替3比用4代替1的总成本要低。
https://stackoverflow.com/questions/43480085
复制相似问题