algorithm
Kruskal-Algorithmus

Bemerkungen

Einfach, detailliertere Implementierung

Um Zykluserfassung effizient zu handhaben, betrachten wir jeden Knoten als Teil eines Baumes. Wenn eine Kante hinzufügen, überprüfen wir, ob die beiden Komponentenknoten Teil verschiedenen Bäume sind. Zunächst macht jeder Knoten einen mit einem Knoten Baum.

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

Einfache, unzusammenhängende Implementierung

Bei der obigen Gesamtstrukturmethode handelt es sich eigentlich um eine disjunkte Datenstruktur, die drei Hauptoperationen umfasst:

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)

Diese naive Implementierung führt zu einer O(n log n) Zeit zum Verwalten der disjunkt-gesetzten Datenstruktur, was zu einer O(m*n log n) Zeit für den gesamten Kruskal-Algorithmus führt.

Optimale, unzusammenhängende Implementierung

Wir können zwei Dinge tun, um die einfachen und suboptimalen Subalgorithmen für disjunkte Sets zu verbessern:

1. Heuristik der findSet : findSet muss niemals einen Baum mit einer Höhe von mehr als 2 . Wenn ein solcher Baum durchlaufen wird, kann er die unteren Knoten direkt mit der Wurzel verknüpfen, wodurch zukünftige Durchquerungen optimiert werden.

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

2. Höhenbasierte Zusammenführungsheuristik : Speichern Sie für jeden Knoten die Höhe des Teilbaums. Machen Sie beim Zusammenführen den größeren Baum zum übergeordneten Element des kleineren Baums und erhöhen Sie dadurch nicht die Körpergröße.

   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
   

Dies führt zu einer O(alpha(n)) Zeit für jede Operation, wobei alpha das Inverse der schnell wachsenden Ackermann-Funktion ist, also sehr langsam wächst und für praktische Zwecke als O(1) werden kann.

Dies macht den gesamten Kruskal-Algorithmus aufgrund der anfänglichen Sortierung zu O(m log m + m) = O(m log m) .

Hinweis

Die Komprimierung von Pfaden kann die Höhe des Baums reduzieren. Daher ist das Vergleichen der Baumhöhen während der Vereinigungsoperation keine triviale Aufgabe. Um die Komplexität des Speicherns und Berechnens der Höhe der Bäume zu vermeiden, kann das resultierende übergeordnete Element zufällig ausgewählt werden:

    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 der Praxis führt dieser randomisierte Algorithmus zusammen mit der Pfadkomprimierung für die findSet Operation zu einer vergleichbaren Leistung, die jedoch viel einfacher zu implementieren ist.

Einfache Implementierung auf hohem Niveau

Sortieren Sie die Kanten nach Wert und fügen Sie jede MST in sortierter Reihenfolge hinzu, wenn kein Zyklus erstellt wird.

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