[理工] 算法最小生成树 wacheck PTT批踢踢实业坊

[理工] 算法最小生成树

楼主: wacheck (94不爱喝水) 2018-11-26 20:44:09

大家好
想请问一下这一题
https://i.imgur.com/aqJROK0.png
这题答案是c
(这个算法应该是prims算法吧)
我想请问a,b两个选项错在哪里?
最小生成树不是当边的weight都不同时会唯一吗?
(莫非错在if and only以及 only if吧..)
感谢大家了

作者: f255577 (沈大妈) 2018-11-26 21:22:00

思考方向改成就算有相同权重，K也还是MST

作者: wei12f8158 (WEI) 2018-11-26 21:23:00

题目是问是否唯最小生成树，不是问唯一

楼主: wacheck (94不爱喝水) 2018-11-26 22:05:00

澄清一下我的理解：所以意思是不管有无相同权重的边执行此算法都会得到MST 是这样吗@@

作者: f255577 (沈大妈) 2018-11-26 22:53:00

是的

楼主: wacheck (94不爱喝水) 2018-11-27 23:31:00

感恩

继续阅读

[理工] 计组张凡下册 p.140paralyzation [理工] 中正资结rex51920594 [理工] 计组上册 p.457wei12f8158 [理工] 离散生成函数eggy1018 [理工] 资结Heap SortANANquenchan [理工] [计组] 下册p.22&p.23guanhao1370 计组张凡下册p.10 memoryparalyzation [理工] 离散整数分割jojoboy0115 [理工] (logn)! 与 log(n!)哪个成长率高,大Dora5566 [理工] 107交大资结x06942l4

Contact Us: admin [ a t ] ucptt.com