是否有一種算法可以在只有k個不同邊緣成本的圖上找到運行時間爲O（n log k）的最小生成樹？

這樣的算法在Skiena的算法設計書中作爲練習留給讀者，據推測它只是Prim算法的修改（In his wiki reference練習6-11）。任何人都可以設計此類算法是否有一種算法可以在只有k個不同邊緣成本的圖上找到運行時間爲O（n log k）的最小生成樹？

2011-02-17 ilcavero

什麼是正？ n = | V | + | E |？ – 2011-02-17 22:24:00

n = | V |根據我的理解 – ilcavero 2011-02-18 03:51:56

具有簡單優先級隊列的Prim是O（m + n lg n），其中m是邊數，n是頂點數。如果您存儲具有相同優先級的條目（例如，使用鏈接列表），則會自動獲得O（m + n lg k）。 AFAIK，這種情況下最先進的是O（m），Fredman and Willard。

2011-02-17 22:56:26

只需要清楚，我相信問題中的O（n lg k）是錯誤的。事實上，我在Skiena的書 – 2011-02-17 22:58:08

是的，問題應該要求O（m + n log k）。很明顯，歐米茄（米）是一個下界，因爲我們甚至不檢查所有這些都找不到最低權重的邊緣。

爲了記錄，約定是n表示頂點的數量，m表示邊的數量。

享受我的書:-)

史蒂芬Skiena

2011-02-18 14:11:33

回答