作者NOtWorThy (天意不可微 可微则连续)
看板Grad-ProbAsk
标题[理工] DS - Kruskal's演算法
时间Mon Jun 1 00:43:47 2009
如题
G = (V, E)
先从E中找最小的边,若此边加入不会造成cycle,就将它加入
直到含有n-1个边
我是觉得有点疑虑
因为他这样为什麽能确保找到的一定是最小成本扩张树?
会不会有一种可能
Step i 找到的边虽然是当下最好选择
而且它会影响到 Step i+1的选择
而影响到有更好的选择没被找到?
这个演算法有没有证明伊定可以 Work ??
烦请先进解惑~~
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.91.18
1F：推 Gaogaigar:cormen那本有证明o_o 06/01 03:40
2F：推 Gaogaigar:我记得好像是反证法~你可以试看看 06/01 03:42
3F：→ ssccg:演算法的正确性都是有证明的，没证明过的根本就不是演算法 06/01 12:07
4F：→ NOtWorThy:谢谢楼上~ 06/01 12:19
5F：→ awpadam:证明看不懂可以寄站内信问我。 06/01 18:52
6F：推 swon:参考 14059 06/02 00:49