[理工] DS - Kruskal's演算法

看板Grad-ProbAsk作者NOtWorThy (天意不可微可微則連續)時間15年前 (2009/06/01 00:43)推噓3(3推 0噓 3→)

留言6則, 5人參與討論串1/1

如題 G = (V, E) 先從E中找最小的邊,若此邊加入不會造成cycle,就將它加入直到含有n-1個邊我是覺得有點疑慮因為他這樣為什麼能確保找到的一定是最小成本擴張樹? 會不會有一種可能 Step i 找到的邊雖然是當下最好選擇而且它會影響到 Step i+1的選擇而影響到有更好的選擇沒被找到? 這個演算法有沒有證明伊定可以 Work ?? 煩請先進解惑~~ 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.91.18

推

Gaogaigar

06/01 03:40, , 1^F

06/01 03:40, 1^F

推

Gaogaigar

06/01 03:42, , 2^F

06/01 03:42, 2^F

→

ssccg

06/01 12:07, , 3^F

06/01 12:07, 3^F