algorithm
Kruskals algoritm

Anmärkningar

Enkel, mer detaljerad implementering

För att effektivt hantera cykeldetektering anser vi varje nod som en del av ett träd. När vi lägger till en kant kontrollerar vi om dess två komponentnoder är en del av distinkta träd. Ursprungligen utgör varje nod ett träd med en nod.

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

Enkel, osammanhängande implementering

Ovanstående skogsmetodik är faktiskt en osammanhängande datastruktur, som involverar tre huvudoperationer:

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)

Denna naiva implementering leder till O(n log n) tid för att hantera den osammanhängande uppsatta datastrukturen, vilket leder till O(m*n log n) tid för hela Kruskals algoritm.

Optimal, osammanhängande implementering

Vi kan göra två saker för att förbättra de enkla och suboptimala sammanhängande subalgoritmerna:

1. Sökvägskomprimering heuristisk : findSet behöver inte någonsin hantera ett träd med en höjd större än 2 . Om det slutar att iterera ett sådant träd kan det koppla de nedre noderna direkt till roten och optimera framtida traversals;

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

2. Höjdbaserad sammanslagande heuristik : lagra höjden på undertråden för varje nod. Vid sammanslagning, gör det högre trädet till moder till det mindre och ökar inte någons höjd.

   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
   

Detta leder till O(alpha(n)) tid för varje operation, där alpha är det omvända för den snabbväxande Ackermann-funktionen, så att den är väldigt långsam växande och kan betraktas som O(1) för praktiska ändamål.

Detta gör hela Kruskals algoritm O(m log m + m) = O(m log m) grund av den ursprungliga sorteringen.

Notera

Väggkomprimering kan minska trädets höjd, varför det inte är en triviell uppgift att jämföra höjderna på träden under föreningsfunktionen. För att undvika komplexiteten i att lagra och beräkna höjden på träden kan den resulterande föräldern plockas slumpmässigt:

    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

I praktiken kommer denna slumpmässiga algoritm tillsammans med findSet för findSet drift att resultera i jämförbara prestanda, men ändå mycket enklare att implementera.

Enkel implementering på hög nivå

Sortera kanterna efter värde och lägg till var och en till MST i sorterad ordning, om det inte skapar en cykel.

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