基於最佳脫節集的實現

我們可以做兩件事來改進簡單和次優的不相交集子演算法:

  1. 路徑壓縮啟發式findSet 不需要處理高度大於 2 的樹。如果它最終迭代這樣一棵樹,它可以將較低的節點直接連結到根,優化未來的遍歷;

    subalgo findSet(v: a node):
        if v.parent != v
            v.parent = findSet(v.parent)
        return v.parent
    
  2. 基於高度的合併啟發式 :對於每個節點,儲存其子樹的高度。合併時,讓較高的樹成為較小樹的父母,從而不會增加任何人的身高。

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)
    
        if vRoot == uRoot:
            return
    
        if vRoot.height < uRoot.height:
            vRoot.parent = uRoot
        else if vRoot.height > uRoot.height:
            uRoot.parent = vRoot
        else:
            uRoot.parent = vRoot
            uRoot.height =  uRoot.height + 1
    

這導致每次操作的時間為 3h,其中 alpha 是快速增長的 Ackermann 函式的倒數,因此它的生長非常緩慢,並且可以被認為是實際目的的 O(1)

由於初始排序,這使得整個 Kruskal 的演算法 O(m log m + m) = O(m log m)

注意

路徑壓縮可能會降低樹的高度,因此在聯合操作期間比較樹的高度可能不是一項簡單的任務。因此,為了避免儲存和計算樹高的複雜性,可以隨機選擇生成的父級:

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)

        if vRoot == uRoot:
            return
        if random() % 2 == 0:
            vRoot.parent = uRoot
        else:
            uRoot.parent = vRoot

實際上,這種隨機演算法與 findSet 操作的路徑壓縮一起將產生可比較的效能,但實現起來要簡單得多。