algorithm
Algoritme van Kruskal

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
Zoeken…


Opmerkingen

Het algoritme van Kruskal is een hebzuchtig algoritme dat wordt gebruikt om de Minimum Spanning Tree (MST) van een grafiek te vinden. Een minimale overspannende boom is een boom die alle hoekpunten van de grafiek verbindt en het minimale totale randgewicht heeft.

Het algoritme van Kruskal doet dit door herhaaldelijk randen met minimaal gewicht te selecteren (die nog niet in de MST zijn) en deze toe te voegen aan het eindresultaat als de twee hoekpunten verbonden door die rand nog niet zijn verbonden in de MST, anders slaat het die rand over. Union - Zoek datastructuur kan worden gebruikt om te controleren of twee hoekpunten al zijn verbonden in de MST of niet. Een paar eigenschappen van MST zijn als volgt:

  1. Een MST van een grafiek met n hoekpunten heeft exact n-1 randen.
  2. Er bestaat een uniek pad van elk hoekpunt naar elk ander hoekpunt.

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


Modified text is an extract of the original Stack Overflow Documentation
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow