Notizen

Kruskal-Algorithmus

tagsgraphentheorie

Der Kruskal-Algorithmus ist ein Greedy-Algorithmus, der für zusammenhängende gewichtete Graphen den minimalen Spannbaum ermittelt.

Idee

  • Sortiere alle Kanten aufsteigend nach Gewicht
    • Falls zwei Kanten das gleiche Gewicht haben, ist es egal, welche zuerst kommt
  • Übernehme alle Knoten
  • Füge die sortierten Kanten aufsteigend nacheinander ein
    • Falls ein Zyklus entstehen würde, überspringe diese

Überprüfung auf Zyklen

  • Beim stück-für-stück Verbinden der Knoten entstehen Teilgraphen.
  • Jeder Teilgraph wird als Menge gespeichert. (Am Anfang besteht jeder Teilgraph aus nur einem Knoten)
  • Für jede Kante wird überprüft, ob sie einen Knoten aus einer Menge mit einem Knoten aus der selben Menge verbindet.
    • Wenn dem so ist, wird sie übersprungen.
    • Wenn nicht, wird die Kante eingefügt, und die beiden Mengen werden vereinigt.

Laufzeitoptimierung

  • Die Mengen können als verkettete Listen oder Felder implementiert werden.
  • ErzeugeMenge(v) hat immer die Laufzeit .
  • Dann ist die Worst Case-Laufzeit zum Finden der Menge Menge(u) und zum Mengenvereinigen Vereinige(u, v) aber (schlecht).
  • Implementiert man die Mengen aber mit invertierten Bäumen, verbessert sich die Laufzeit.

Union-Find-Datenstruktur

Die Speicherung, Suche und Vereinigung von Mengen kann mittels invertierten Bäumen realisiert werden. Dabei ist jede Menge ein Baum, repräsentiert durch die Wurzel des Baumes.

Beispiel:

graph BT
    V1 --> V1
    V4 --> V1

    V0 --> V2
    V3 --> V2
    V2 --> V5
    V5 --> V5
  • Versuch, Kante V3 - V5 einzufügen würde fehlschlagen, da V3 Teil der Menge mit dem Repräsentanten V5 ist und V5 auch Teil der Menge mit dem Repräsentanten V5 ist.
  • Kante V4 - V2 einzufügen würde funktionieren, da V4 Teil der Menge V1 ist und V2 Teil der Menge V5 ist, also unterschiedliche Mengen.
    • Zeichne also die Kante
    • Vereinige die Mengen V1 und V5: Füge die Bäume zusammen
graph BT
    V1 --> V5
    V4 --> V1

    V0 --> V2
    V3 --> V2
    V2 --> V5
    V5 --> V5

Beachte

Die Bäume zur Mengenspeicherung sind nicht zu verwechseln mit dem entstehenden Spannbaum.

  • Sind die invertierten Bäume möglichst breit und nicht tief, ist die Überprüfung auf Zyklen in Laufzeit möglich.

Verbesserung bei der Vereinigung

  • Geordnete Vereinigung: Beim Vereinigen wird der kleinere Baum an die Wurzel des höheren Baumes angehängt
  • Pfadverkürzung: Beim sich “hochhangeln” wird das Blatt mitgenommen und direkt an die Wurzel gehängt, so dass für das nächste mal der Pfad zur Wurzel kürzer ist. Im Idealfall hängen alle Knoten, die zu einer Menge gehören, direkt an der Wurzel.
    • Dabei ändert sich Laufzeittechnisch nur die Konstante, dennoch kann man insbesondere bei dichten Graphen davon profitieren.

Beide Varianten verbessern die Laufzeit auf .

Implememtierung

Pseudocode

Seien ein Graph und eine Gewichtung.

  • Algorithmus MST_Kruskal(, )
    • Starte mit dem MST =
    • Für jeden Knoten :
      • ErzeugeMenge(v)
    • Sortiere Kanten aufsteigend ihres Gewichts
    • Für jede Kante {u, v} nach aufsteigendem Gewicht
      • Falls Menge(u) Menge(v):
        • MST = MST {{u, v}}
        • Vereinige(u, v)

Laufzeit

  • Für jeden Knoten Menge erzeugen - mal
  • Kanten nach Gewicht sortieren (mit Merge Sort oder 2 Sortieralgorithmen) -
  • Für jede Kante nach aufsteigendem Gewicht - mal
    • Gleichheit der Mengen checken -
    • Ggf. Kante zum Spannbaum hinzufügen -
    • Ggf. Mengen vereinigen -

Insgesamt ergibt sich eine Laufzeit von:

Backlinks