MST的線性時間算法

Question

我想知道是否有人可以指出一個線性時間算法來找到圖的MST時，有一小部分權重（I.e邊只能有2個不同的權重）。

除了Prim's，Kruskal's，Boruvka之外，我在google上找不到任何東西，除了這些特殊情況，似乎沒有任何特性會減少運行時間。我猜測要做線性時間，它必須是對BFS的一種修改（當權重是統一的時候發現MST）。

Answer 1

Prim的O(V lg V)運行時中lg V因素的原因是用於查找下一個候選邊的堆。我非常肯定可以設計一個優先級隊列，在有限數量的權重下可以在固定時間內進行插入和刪除操作，這會將Prim減少到O(V)。

對於優先級隊列，我相信只要數組的索引涵蓋所有可能的權重就可以了，其中每個元素都指向一個包含具有該權重的元素的鏈接列表。找出將下一個元素從哪個列表中取出（「最低」的非空元素），您仍然有一個因子d（不同權重的數量），但如果d是常數，那麼您將沒事的。

Answer 2

詳細闡述Aasmund Eldhuset的答案：如果MST中的權重限制在0,1,2,3，...，U-1範圍內的數字，那麼您可以調整許多現有的算法以運行在（近）線性時間內，如果U是一個常數。

例如，我們來看看Kruskal的算法。 Kruskal算法的第一步是將邊緣按照重量的升序排序。如果您使用基數排序，如果您使用計數排序或時間O（m lg U），則可以及時進行O（m + U）。如果U是常數，那麼這兩個排序步驟都需要線性時間。因此，在這種情況下運行Kruskal算法的運行時間爲O（m α（m）），其中α（m）是逆阿克曼函數，因爲限制因素將是維護不相交集林的運行時。

或者，查看Prim的算法。您需要維護到節點的候選距離的優先級隊列。如果你知道所有的邊都在[0，U）的範圍內，那麼你可以通過存儲一個U桶的數組，一個可能的優先級，以超級天真的方式做到這一點。插入優先級隊列後，只需要將一個項目轉儲到正確的存儲桶中。你可以通過驅逐一個元素並將它移動到一個更低的桶來做一個減少鍵。然後，您可以通過掃描桶來完成find-min。這導致算法運行時間爲O（m + nU），如果U是常數，則它是線性的。