哈哈，原來是NP-Complete問題，難怪特別難想。 :)
是我太孤陋寡聞了，真是不好意思。
既然有關鍵字了，我就可以自己上網查點資料了。
謝謝你啦！
另外再請教一個問題，
如果這個圖是位在二維平面上，且cost都滿足距離的定義，
當距離分別為 Euclidean distance 和 city block distance 時，
這個問題會不會有多項式時間解？
※ 引述《tkcn (小安)》之銘言：
: http://en.wikipedia.org/wiki/K-minimum_spanning_tree
: This problem is known to be NP-complete.
: 看來只能用 heuristic 囉
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.90.81