首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >从加权图中求次最佳最小生成树的算法

问从加权图中求次最佳最小生成树的算法
EN

Stack Overflow用户
提问于 2017-04-18 18:53:09
回答 2查看 1.4K关注 0票数 0

我试图从加权无向图中求出第二次最佳最小跨越3。我知道如何使用Kruskal算法计算MST,我正在考虑这样找到第二最佳最小算法:

步骤:

  1. 对所有的图形边进行排序。
  2. 用Kruskal计算MST
  3. 从不在第一个MST中的图中获取最小权重边,并将其添加到MST (现在MST有了一个循环)
  4. 消除新成形循环中的最大重量边。

这应该是第二好的MST对吧?

顺便说一下,我知道有一个主题指出了一个算法,它在每个MST边之间迭代,然后在图上运行Kruskal,而没有选择边缘,我只是在问我的算法是否有效。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2017-04-18 19:10:30

它不起作用。

在步骤3之后,新添加的边缘可能成为只包含非常低成本的边缘的循环的一部分,因此在步骤3和步骤4之后,MST的总成本会显著增加。

另一方面,该图形可能包含另一个边缘,其成本与步骤3中选择的边缘相似,当添加到MST中时,它将是另一个周期的一部分,例如,包含成本相对较高的边缘。为步骤3选择此边缘,然后应用步骤4将导致另一个生成树,比所提出的算法生成的生成树更好。

票数 1
EN

Stack Overflow用户

发布于 2017-04-18 19:11:11

不,你的算法不管用。

代码语言:javascript
复制
  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代替1的总成本要低。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/43480085

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档