邊緣長度受限時的最小生成樹的快速算法？

假設您有一個帶有非負整數邊長的有向圖，其範圍爲0到U - 1（含）。計算此圖的最小生成樹的最快算法是什麼？我們仍然可以使用現有的最小生成樹算法，例如Kruskal算法O（m log n））或Prim算法（O（m + n log n））。但是，對於U很小的情況，我認爲應該可以做得更好。邊緣長度受限時的最小生成樹的快速算法？

是否有任何算法與更傳統的MST算法競爭，這些算法能夠利用邊緣長度限制在某個範圍內的事實？

謝謝！

來源

2012-01-15 templatetypedef

長度是否也限制爲整數，或僅限於該範圍？ – harold 2012-01-15 23:44:55

@ harold-他們是整數。我會發佈一個更正。 – templatetypedef 2012-01-15 23:45:11

有幾位消息人士提到這是一個線性時間算法，但鏈接到我無法查看的東西。 – harold 2012-01-15 23:48:56

Fredman-Willard在單位成本RAM上給出了整數邊長的O（m + n）算法。 Chazelle給出了一個O（m alpha（m，n）+ n）算法，可以說沒有太多的改進：沒有對邊長的限制（即長度是僅支持比較的不透明數據類型）（α是逆阿克曼函數），Karger-Klein-Tarjan給出了隨機O（m + n）算法。

我不認爲達倫的想法導致O（m + n + U）時間算法。 Jarnik（「Prim」）不單獨使用其優先級隊列，因此可能會多次掃描存儲桶; Kruskal需要一個不相交集數據結構，它不能是O（m + n）。

來源

2012-01-16 18:22:44 Wally

使用整數邊緣權重，可以使用分段來實現優先級隊列，最壞情況下的複雜度爲O(1)，但額外的O(U)空間複雜度。

在您提到的MST算法中，您應該能夠用此整數結構替換基於比較的優先級隊列，並因此刪除複雜性要求中的O(log(n))依賴關係。我希望你最終會在O(n + m)的風格中獲得整體的複雜性。

基本上你設置與該桶相關的一組成本的壓縮鏈表，其中每個列表由索引（整數！）：

struct bucket_list 
{ 
    _cost; // array[0..N-1] holding current cost for each item 

    _head; // array[0..U-1] holding index of first item in each bucket 

    _next; // array[0..N-1] where _next[i] is the next item 
      // in a list for the ith item 

    _prev; // array[0..N-1] where _prev[i] is the last item 
      // in a list for the ith item 
};

這種結構是基於一個事實，即每個項目都一次只能在一個單一的列表中。基於此結構可以實現最壞情況O(1)複雜性對這些操作

：

push(item, cost); // push an item onto the head of the appropriate bucket list 

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list 

update(item, old_cost, new_cost); // move an item between buckets by combining 
            // push and _pop

要使用此結構作爲一個優先級隊列，你只需維護一個指數在目前的最低桶掃描指點。當你想獲得下一個最低成本的物品時，你只需從這個桶中彈出頭部物品。如果存儲桶爲空，則增加存儲桶索引，直至找到非空存儲索引。

當然，如果U變得非常大，那麼額外的空間複雜度以及物品稀疏分佈在桶上的可能性可能使這種方法沒有吸引力。

來源

2012-01-16 00:39:09

此實現的複雜性還包括U，因爲您必須遍歷O（U）存儲桶。 – templatetypedef 2012-01-16 01:58:11

你可以說總複雜度是'O（n + m + U）' - 在整個算法中桶只被遍歷一次，而不是在每一步。 – 2012-01-16 02:07:23

邊緣長度受限時的最小生成樹的快速算法？

回答

相關問題