謝謝你的回覆。 :)
如你所說，這個問題是給定一個圖，並選定一些節點，
然後才要將這些節點兩兩都相連通。
我對你提供的方法還有一些疑問。
當選擇「成本最小的一條路徑」時，
這是指最短路徑嗎？
另外，如果「成本最小的一條路徑」不只一條時，
該選擇哪一條路徑呢？
我再舉個例子：
edge cost
1 <--> 4 2
2 <--> 4 2
3 <--> 4 100
1 <--> 5 3
2 <--> 5 3
3 <--> 5 3
若要將 1 2 3 相連通，最少的 cost 為 9。
依照你的演算法，
如果先選擇了 1-4-2 這一條路徑，
再選擇 1-5-3 這一條路徑，
答案便會是10。
（1-4-2是所有選定的點之間，最短的一條路徑。
1-5-3則是第二短的路徑當中字典順序最小的。）
※ 引述《xu3jp68 (信箱爆炸..XD)》之銘言：
: ※ 引述《DJWS (...)》之銘言：
: : 你誤會題意了。舉個例子：
: : edge cost
: : 1 <--> 2 2
: : 1 <--> 3 2
: : 1 <--> 4 1
: : 2 <--> 3 3
: : 然後讓 2 3 4 這三個節點相連通，所需要的最少 cost 應為 5。
: 假設你要找2,3,4之間最小成本，所以找所有路徑當中跟2,3,4有關的，
: 選成本最小的一條，這邊是1 <--> 4，所以你現在收集了1跟4的點，
: 然後在搜尋有跟1,4當中有關的最小成本，這邊是1 <--> 2 or 1 <--> 3
: 假設你選1 <--> 2，所以你現在手上有1,2,4三個點，然後再搜尋
: 跟1,2,4有關的路徑當中成本最小的，最後得到1 <--> 3，總成本是5
: 所以我覺得應該是一開始你要先輸入你需要哪先點相連，輸入完再讓它
: 搜尋跟這些點有關係當中成本最小的路徑，所以每次搜尋應該就會連起來
: 一個你想要的點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.90.81
※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:15)
※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:19)
※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:23)
※ 編輯: DJWS 來自: 140.112.90.81 (12/23 20:27)