知识卡片
最小生成树可能不唯一
边权相同可能使多棵不同的生成树拥有相同最小总权;因此算法需要保证总权最小,无需保证唯一形状。
图21.1给出换一条边后总权仍为37的实例。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第21章 最小生成树 · 查看原书依据
This minimum spanning tree is not unique: removing the edge (b, c) and replacing it with the edge (a, h) yields another spanning tree with weight 37. The two algorithms are greedy algorithms, as described in Chapter 15. Each step
参考来源
- 位置:《算法导论(第4版)》第21章《最小生成树》(OEBPS/chapter021.xhtml,文本字符[0,5000))。
- 结论依据:图21.1在两条可交换边上给出同权最优树的具体例子。
- 原始内容:This minimum spanning tree is not unique: removing the edge ( b , c ) and replacing it with the edge ( a , h ) yields another spanning tree with weight 37. The two algorithms are greedy algorithms, as described in Chapter 15 . Each step