algorithm
Algoritme van Kruskal

Opmerkingen

Eenvoudige, meer gedetailleerde implementatie

Om cyclusdetectie efficiënt af te handelen, beschouwen we elk knooppunt als onderdeel van een boom. Bij het toevoegen van een rand controleren we of de twee componentenknopen deel uitmaken van verschillende bomen. Aanvankelijk vormt elke knoop een boom met één knoop.

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

Eenvoudige, onsamenhangende set-gebaseerde implementatie

De bovenstaande forest-methode is eigenlijk een onsamenhangende gegevensstructuur, die drie hoofdbewerkingen omvat:

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)

Deze naïeve implementatie leidt tot O(n log n) tijd voor het beheer van de onsamengestelde set datastructuur, wat leidt tot O(m*n log n) tijd voor het gehele algoritme van Kruskal.

Optimale, disjoint-set gebaseerde implementatie

We kunnen twee dingen doen om de eenvoudige en suboptimale disjoint-set subalgoritmen te verbeteren:

1. findSet heuristisch : findSet hoeft nooit een boom te hanteren met een hoogte groter dan 2 . Als het zo'n boom itereert, kan het de onderste knooppunten direct aan de wortel koppelen, waardoor toekomstige doorvoer wordt geoptimaliseerd;

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

2. Op hoogte gebaseerde samenvoegingsheuristiek : sla voor elke knoop de hoogte van de substructuur op. Maak bij het samenvoegen de langere boom de ouder van de kleinere, en vergroot dus niemand.

   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
   

Dit leidt tot O(alpha(n)) tijd voor elke bewerking, waarbij alpha het omgekeerde is van de snelgroeiende Ackermann-functie, dus het is zeer langzaam groeiend en kan voor praktische doeleinden als O(1) worden beschouwd.

Dit maakt het gehele algoritme van Kruskal O(m log m + m) = O(m log m) , vanwege de initiële sortering.

Notitie

Padcompressie kan de hoogte van de boom verminderen, waardoor het vergelijken van hoogten van de bomen tijdens het verenigingsbedrijf misschien geen triviale taak is. Om de complexiteit van het opslaan en berekenen van de hoogte van de bomen te voorkomen, kan de resulterende ouder willekeurig worden gekozen:

    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

In de praktijk zal dit gerandomiseerde algoritme samen met findSet voor findSet werking resulteren in vergelijkbare prestaties, maar veel eenvoudiger te implementeren.

Eenvoudige implementatie op hoog niveau

Sorteer de randen op waarde en voeg ze toe aan de MST in gesorteerde volgorde, als er geen cyclus ontstaat.

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