algorithm
Algorytm Kruskala

Uwagi

Prosta, bardziej szczegółowa implementacja

Aby skutecznie obsługiwać wykrywanie cyklu, uważamy każdy węzeł za część drzewa. Podczas dodawania krawędzi sprawdzamy, czy jej dwa węzły składowe są częścią odrębnych drzew. Początkowo każdy węzeł tworzy drzewo z jednym węzłem.

algorithm kruskalMST'(G: a graph)
    sort G's edges by their value
    MST = a forest of trees, initially each tree is a node in the graph
    for each edge e in G:
        if the root of the tree that e.first belongs to is not the same 
        as the root of the tree that e.second belongs to:
            connect one of the roots to the other, thus merging two trees
    
    return MST, which now a single-tree forest

Prosta implementacja oparta na rozłącznych zestawach

Powyższa metodologia lasu jest w rzeczywistości rozłączną strukturą danych, która obejmuje trzy główne operacje:

subalgo makeSet(v: a node):
    v.parent = v    <- make a new tree rooted at v
    

subalgo findSet(v: a node):
    if v.parent == v:
        return v
    return findSet(v.parent)

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

    uRoot.parent = vRoot

algorithm kruskalMST''(G: a graph):
    sort G's edges by their value
    for each node n in G:
        makeSet(n)
    for each edge e in G:
        if findSet(e.first) != findSet(e.second):
            unionSet(e.first, e.second)

Ta naiwna implementacja prowadzi do czasu O(n log n) na zarządzanie strukturą danych rozłącznych, prowadząc do czasu O(m*n log n) dla całego algorytmu Kruskala.

Optymalna implementacja oparta na rozłącznych zestawach

Możemy zrobić dwie rzeczy, aby poprawić proste i nieoptymalne pod-algorytmy rozłączne:

1. Heurystyka kompresji ścieżki : findSet nie musi nigdy obsługiwać drzewa o wysokości większej niż 2 . Jeśli zakończy iterację takiego drzewa, może połączyć dolne węzły bezpośrednio z korzeniem, optymalizując przyszłe przejścia;

   subalgo findSet(v: a node):
       if v.parent != v
           v.parent = findSet(v.parent)
       return v.parent
   

2. Heurystyka scalania oparta na wysokości: dla każdego węzła zapisz wysokość jego poddrzewa. Podczas łączenia uczyń wyższym drzewem rodzicem mniejszego, nie zwiększając w ten sposób wzrostu.

   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
   

Prowadzi to do czasu O(alpha(n)) dla każdej operacji, gdzie alpha jest odwrotnością szybko rosnącej funkcji Ackermanna, a zatem rośnie bardzo wolno i można ją uznać za O(1) ze względów praktycznych.

To sprawia, że cały algorytm Kruskala O(m log m + m) = O(m log m) , z powodu początkowego sortowania.

Uwaga

Kompresja ścieżki może zmniejszyć wysokość drzewa, dlatego porównywanie wysokości drzew podczas operacji łączenia może nie być łatwym zadaniem. Aby uniknąć złożoności przechowywania i obliczania wysokości drzew, rodzicielski rodzic może zostać wybrany losowo:

    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

W praktyce ten randomizowany algorytm wraz z kompresją ścieżki dla operacji findSet zapewni porównywalną wydajność, ale znacznie prostszą do wdrożenia.

Proste wdrożenie na wysokim poziomie

Posortuj krawędzie według wartości i dodaj je do MST w posortowanej kolejności, jeśli nie tworzy to cyklu.

algorithm kruskalMST(G: a graph)
    sort G's edges by their value
    MST = an empty graph
    for each edge e in G:
        if adding e to MST does not create a cycle:
            add e to MST

    return MST