[問題] 一個圖論的問題 (K-MST)

看板Prob_Solve作者DJWS (...)時間18年前 (2007/12/22 11:57)推噓0(0推 0噓 0→)

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

給定一個無向圖，edge都有cost。現在在圖上已選定了一些節點，我們想要把這些節點連接起來，讓它們兩兩都相連通。請問最少的cost為多少？這個問題跟minimum spanning tree的差別是， minimum spanning tree需要串起圖上所有節點，而這個問題只需串起選定的節點即可。請問這個問題該如何解決？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.90.81