algorithm
Kruskals algoritm

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
Sök…


Anmärkningar

Kruskals algoritm är en girig algoritm som används för att hitta Minimum Spanning Tree (MST) i en graf. Ett lägsta spännträd är ett träd som förbinder alla vertikorns kurvor och har den lägsta totala vikten.

Kruskals algoritm gör det genom att upprepade gånger plocka ut kanter med minsta vikt (som inte redan finns i MST) och lägga till dem till det slutliga resultatet om de två hörn som är anslutna med den kanten ännu inte är anslutna i MST, annars hoppar den den kanten. Union - Find datastruktur kan användas för att kontrollera om två hörn redan är anslutna i MST eller inte. Några egenskaper hos MST är följande:

  1. En MST för en graf med n hörn har exakt n-1 kanter.
  2. Det finns en unik väg från varje topp till varje annan topp.

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


Modified text is an extract of the original Stack Overflow Documentation
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow