Kruskal-Algorithmus Rechner

Pseudocode

Sortiere alle Kanten nach Gewicht und gehe die Liste durch, wobei jede Kante hinzugefügt wird, die zwei verschiedene Komponenten verbindet. Union-Find macht die Prüfung auf "verschiedene Komponenten" nahezu kostenlos.

Kruskal(graph):
    sortiere alle Kanten aufsteigend nach Gewicht
    makeSet(v) für jeden Knoten v
    mst = []

    für jede Kante (u, v, w) in sortierter Reihenfolge:
        wenn find(u) != find(v):    // verschiedene Komponenten
            union(u, v)
            mst.anhängen((u, v, w))
            wenn mst V - 1 Kanten hat: abbrechen

    gib mst zurück

Kruskal lässt einen Wald wachsen, keinen Baum. Mehrere unverbundene Fragmente entwickeln sich unabhängig und verschmelzen, sobald billige Kanten sie verbinden; das ist der strukturelle Unterschied zu Prim und der Grund, warum Kruskal unzusammenhängende Graphen mühelos behandelt: er liefert dann einfach einen minimalen Spannwald. Die Korrektheit folgt aus der Schnitteigenschaft, angewandt auf die Komponentengrenzen, genau wie bei Prim.

Durchgerechnetes Beispiel, Schritt für Schritt

Baue den minimalen Spannbaum auf demselben Graphen wie im Prim-Beispiel, damit sich die beiden Entdeckungsreihenfolgen vergleichen lassen.

Beispielgraph: Ungerichtete Kanten A-B (2), A-C (3), B-C (1), C-D (4) und B-D (7).

1. Kanten sortieren. Nach Gewicht: B-C mit 1, A-B mit 2, A-C mit 3, C-D mit 4, B-D mit 7. Jeder Knoten beginnt in seiner eigenen einelementigen Menge.
2. B-C (1) annehmen. B und C liegen in verschiedenen Mengen, die Kante wird also angenommen und beide verschmelzen. Die Komponenten sind nun {B, C}, {A} und {D}.
3. A-B (2) annehmen. A und B liegen weiterhin in verschiedenen Mengen, also annehmen und verschmelzen. Die Komponenten sind nun {A, B, C} und {D}.
4. A-C (3) ablehnen. A und C liegen inzwischen in derselben Menge, diese Kante würde also einen Zyklus schließen und wird übersprungen. Das ist der sichtbare Unterschied zu Prim, der A-C gar nicht erst als Kandidatin auftauchen ließ, sobald beide Endpunkte im Baum waren.
5. C-D (4) annehmen. C und D liegen in verschiedenen Mengen, also annehmen und verschmelzen. Alle vier Knoten bilden nun eine Komponente und der Baum hat drei Kanten, der Algorithmus kann also aufhören, ohne B-D mit 7 zu prüfen.

Der minimale Spannbaum besteht aus B-C, A-B und C-D mit Gesamtgewicht 1 + 2 + 4 = 7, identisch mit dem, was Prim von A aus lieferte. Die Bäume stimmen überein, wie es bei verschiedenen Kantengewichten sein muss, doch die Entdeckungsreihenfolge unterscheidet sich: Prim ging A-B, B-C, C-D und wuchs von A nach außen, während Kruskal B-C, A-B, C-D in reiner Gewichtsreihenfolge ging und unterwegs ausdrücklich eine zyklusschließende Kante ablehnen musste.

Komplexität und woher sie kommt

Zeit: O(E log E) · Speicher: O(V + E)

Das Sortieren der Kanten dominiert alles Übrige mit O(E log E), was dasselbe ist wie O(E log V), da E höchstens V hoch 2 beträgt und log E somit innerhalb eines konstanten Faktors von log V liegt. Nach dem Sortieren führt die Schleife höchstens 2E find-Operationen und V - 1 union-Operationen aus. Mit Pfadkompression und Union by Rank kostet jede davon die inverse Ackermannfunktion von V, die für jede speicherbare Eingabe unter 5 liegt und als konstant behandelt wird. Der Union-Find-Anteil ist also effektiv O(E) und das Sortieren macht die gesamten Kosten aus. Treffen die Kanten bereits sortiert ein oder lassen sie sich in Eimer einsortieren, weil die Gewichte kleine ganze Zahlen sind, sinkt Kruskal auf nahezu linear und schlägt Prim deutlich.

Wann Kruskal MST-Algorithmus passt und wann nicht

Kruskal und Prim lösen dasselbe Problem. Dichte, Kantenreihenfolge und Zusammenhang entscheiden, welcher besser ist.

Häufige Fehler

• Union-Find ohne Pfadkompression oder Union by Rank verwenden. Eine naive Implementierung entartet zu verketteten Listen und jedes find kostet O(V), was die Schleife auf O(E·V) treibt. Beide Optimierungen sind je wenige Zeilen und machen die nahezu konstante Schranke überhaupt erst real.
• Knoten statt Mengenrepräsentanten vergleichen. Der Zyklustest lautet find(u) != find(v), nicht u != v. Die Knoten selbst zu vergleichen nimmt jede Kante an und erzeugt einen Graphen voller Zyklen statt eines Baums.
• Vergessen, bei V - 1 Kanten aufzuhören. Kein Korrektheitsfehler, aber unnötiger Aufwand: Sobald der Baum V - 1 Kanten hat, ist er vollständig und jede weitere Kante wird abgelehnt. Auf einem dichten Graphen ist das sehr viel verschwendetes Durchsuchen.
• Bei Gewichtsgleichheit eine eindeutige Antwort annehmen. Teilen sich mehrere Kanten ein Gewicht, entscheidet die Sortierreihenfolge, welche genommen werden, und verschiedene Implementierungen liefern verschiedene Bäume gleichen Gesamtgewichts. Prüfe das Gesamtgewicht, nicht die Kantenmenge.
• Ihn auf gerichtete Graphen anwenden. Wie Prim ist Kruskal für ungerichtete Graphen definiert. Das gerichtete Gegenstück ist die minimale spannende Arboreszenz und erfordert den Chu-Liu/Edmonds-Algorithmus.

Häufig gestellte Fragen

Wie funktioniert der Algorithmus von Kruskal?

Er sortiert alle Kanten nach Gewicht und geht die sortierte Liste durch, wobei er eine Kante hinzufügt, wenn ihre beiden Endpunkte in verschiedenen Komponenten liegen, und sie überspringt, wenn sie bereits verbunden sind. Eine Union-Find-Struktur beantwortet die Zusammenhangsfrage in nahezu konstanter Zeit. Nach V - 1 angenommenen Kanten liegt ein minimaler Spannbaum vor.

Wie ist die Zeitkomplexität des Algorithmus von Kruskal?

O(E log E) Zeit, vollständig dominiert vom Sortieren der Kanten. Die Union-Find-Operationen fügen lediglich O(E·α(V)) hinzu, wobei α die inverse Ackermannfunktion und praktisch konstant ist. Sind die Kanten bereits sortiert oder per Bucket-Sort sortierbar, wird der Algorithmus nahezu linear.

Was ist der Unterschied zwischen Kruskal und Prim?

Kruskal betrachtet die Kanten global in Gewichtsreihenfolge und lässt einen Wald wachsen, der zu einem Baum verschmilzt, wobei Union-Find Zyklen ablehnt. Prim lässt einen einzigen zusammenhängenden Baum von einem Startknoten aus mit einer Prioritätswarteschlange wachsen. Kruskal passt zu dünnen oder vorsortierten Graphen und behandelt unzusammenhängende Eingaben von Haus aus; Prim passt zu dichten Graphen.

Warum braucht Kruskal Union-Find?

Weil er von jeder Kante nur wissen will, ob ihre Endpunkte bereits verbunden sind, und diese Frage E-mal gestellt wird. Union-Find beantwortet sie mit Pfadkompression und Union by Rank in nahezu konstanter Zeit. Den Zusammenhang für jede Kante mit einem Durchlauf neu zu berechnen würde stattdessen O(E·V) kosten.

Kann Kruskal einen unzusammenhängenden Graphen verarbeiten?

Ja, ohne Änderungen. Er liefert dann schlicht einen minimalen Spannwald, einen Baum je Zusammenhangskomponente, weil er während des Laufs nie verlangt, dass die angenommenen Kanten eine einzige zusammenhängende Struktur bilden. Prim hingegen hält an, sobald er die Komponente seines Startknotens erschöpft hat.