作者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