Der Algorithmus von Kruskal erklärt

Mohammed Islam Hadjoudj

Experte für Operations Research

1. Einführung in den Algorithmus von Kruskal

Der Algorithmus von Kruskal erzeugt einen minimalen Spannbaum: Aus einem zusammenhängenden, ungerichteten, gewichteten Graphen wählt er die günstigste Kantenmenge, die jeden Knoten berührt, ohne einen Zyklus zu bilden. Bei V Knoten enthält diese Menge stets genau V - 1 Kanten.

Während der Algorithmus von Prim einen einzigen zusammenhängenden Baum von einem Startknoten aus nach außen wachsen lässt, ignoriert Kruskal den Zusammenhang bis fast zum Schluss. Er sortiert sämtliche Kanten des Graphen nach Gewicht, durchläuft diese Liste von der günstigsten zur teuersten und behält jede Kante, sofern sie keinen Zyklus schließt. Mehr wird nicht herangezogen. Es gibt weder einen Startknoten noch einen Begriff von Front.

Die Folge ist, dass Kruskal den größten Teil seines Laufs einen Wald statt eines Baums verwaltet: viele kleine, über den Graphen verstreute Fragmente, die unabhängig voneinander wachsen und verschmelzen und erst mit der allerletzten akzeptierten Kante zu einem einzigen Spannbaum zusammenfinden. Genau dieser Formunterschied lässt ihn sich bei dünn besetzten Graphen, bei unzusammenhängender Eingabe und unter dem Profiler anders verhalten.

2. Warum es funktioniert: die Zykluseigenschaft

Die Korrektheit von Prim beruht auf einem Satz darüber, welche Kanten sicher aufgenommen werden dürfen. Kruskal verbringt ebenso viel Zeit damit, Kanten zu verwerfen, weshalb es sich lohnt, den Gegenstücksatz zu benennen, der ein Wegwerfen rechtfertigt.

Der Beweis spiegelt jenen der Schnitteigenschaft. Angenommen, die schwerste Kante e eines Zyklus gehörte doch zu einem minimalen Spannbaum T. Entfernt man e aus T, zerfällt dieser in zwei Komponenten. Der Rest des Zyklus verläuft weiterhin zwischen diesen beiden Komponenten, also verbindet sie eine andere Zykluskante f wieder. Setzen Sie f stattdessen ein. Sie haben erneut einen Spannbaum, und da e strikt die schwerste war, ist der neue Baum strikt leichter, im Widerspruch zur Annahme, T sei minimal.

Sehen Sie nun, was geschieht, wenn Kruskal eine Kante verwirft. Er erreicht die Kante e und stellt fest, dass beide Endpunkte bereits im selben Fragment liegen. Also existiert zwischen ihnen bereits ein Weg, gebaut ausschließlich aus zuvor akzeptierten Kanten, mithin aus Kanten, die nicht schwerer als e sind. Das Hinzufügen von e würde einen Zyklus schließen, auf dem e das schwerste Glied ist. Nach der Zykluseigenschaft kostet das Verwerfen nichts.

Die akzeptierten Kanten sind aus demselben Grund sicher wie bei Prim. Verbindet eine Kante zwei verschiedene Fragmente, so ist sie die günstigste verbliebene Kante über den Schnitt, der ein Fragment vom Rest trennt, und die Schnitteigenschaft greift unverändert. Kruskal ist in beide Richtungen gierig, und beide Richtungen sind Sätze.

3. Wie der Wald verschmilzt

Konkret hält der Algorithmus zu Beginn jeden Knoten in einem eigenen Fragment: V Fragmente, null Kanten. Beim Durchlaufen der sortierten Kantenliste stellt er an jede Kante (u, v) genau eine Frage:

• Liegen u und v bereits im selben Fragment? Dann würde die Kante einen Zyklus schließen. Verwerfen und weitergehen.
• Liegen sie in verschiedenen Fragmenten? Dann die Kante aufnehmen und die beiden Fragmente zu einem verschmelzen.

Jede aufgenommene Kante verringert die Zahl der Fragmente um genau eins. Von V Fragmenten auf eines zu kommen bedeutet also genau V - 1 Aufnahmen, und das ist die Abbruchbedingung. Sind so viele erreicht, wird jede verbleibende Kante der Liste garantiert verworfen, die Schleife darf also vorzeitig enden.

Damit reduziert sich der gesamte Algorithmus auf eine einzige Datenstrukturfrage: Wie prüft man millionenfach schnell "gleiches Fragment?" und "verschmelze diese beiden Fragmente"? Genau das leistet Union-Find.

4. Schritt für Schritt durchgerechnet

Nehmen wir den Graphen mit sechs Knoten, der sich durch unseren Leitfaden zu minimalen Spannbäumen zieht. Seine neun Kanten sind:

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

Nach Gewicht sortiert ergibt sich die Reihenfolge, die der Algorithmus tatsächlich abläuft:

A-C 1   B-C 2   D-E 2   E-F 3   A-B 4   B-D 5   C-D 6   C-E 7   D-F 8

Jeder Knoten beginnt für sich allein, der Wald startet also als {A} {B} {C} {D} {E} {F}.

1. A-C (1). Aufnehmen. Verschiedene Fragmente. Der Wald wird zu {AC} {B} {D} {E} {F}. Laufende Summe 1.
2. B-C (2). Aufnehmen. B steht allein, C ist bei A. Der Wald wird zu {ABC} {D} {E} {F}. Summe 3.
3. D-E (2). Aufnehmen. Beachten Sie, dass hier ein Fragment fernab des ersten entsteht. Der Wald wird zu {ABC} {DE} {F}. Summe 5.
4. E-F (3). Aufnehmen. Der Wald wird zu {ABC} {DEF}. Summe 8.
5. A-B (4). Verwerfen. A und B liegen beide bereits in {ABC}, dies würde also den Zyklus A-C-B-A schließen. Verworfen.
6. B-D (5). Aufnehmen. Diese Kante überbrückt die beiden verbliebenen Fragmente. Der Wald wird zu {ABCDEF}. Summe 13.

Fünf Kanten für sechs Knoten aufgenommen, der Algorithmus hält also an, ohne C-D (6), C-E (7) oder D-F (8) je zu betrachten. Der entstandene Baum besteht aus A-C (1), B-C (2), D-E (2), E-F (3), B-D (5) mit einem Gesamtgewicht von 13, genau dem Baum, den Prim auf demselben Graphen findet.

Schritt 3 ist der Moment, der diesen Algorithmus auszeichnet. Prim hätte D-E an dieser Stelle nicht nehmen können, weil keiner ihrer Endpunkte seinen wachsenden Baum berührte. Kruskal ist das gleichgültig: Er beginnt bereitwillig ein zweites, unabhängiges Fragment auf der anderen Seite des Graphen und kümmert sich später um die Verbindung. Und Schritt 5 zeigt die Zykluseigenschaft in Aktion, indem er genau jene Kante verwirft, die auf dem entstehenden Zyklus die schwerste ist.

5. Union-Find: die Struktur, die es schnell macht

Der naive Weg, zu prüfen, ob zwei Knoten bereits verbunden sind, ist eine Traversierung von einem aus, um zu sehen, ob man den anderen erreicht. Das kostet O(V) je Kante und zieht den gesamten Algorithmus auf O(V * E) herunter, schlechter als die Sortierung, die es eigentlich ergänzen sollte.

Union-Find, auch Union-Find-Struktur für disjunkte Mengen genannt, beantwortet beide Fragen in nahezu konstanter Zeit. Sie verwaltet jedes Fragment als Baum aus Elternzeigern mit einem Repräsentanten an der Wurzel und stellt zwei Operationen bereit:

• find(x) liefert den Repräsentanten von x' Fragment. Zwei Knoten liegen genau dann im selben Fragment, wenn ihre Repräsentanten identisch sind.
• union(x, y) verschmilzt die beiden Fragmente, indem eine Wurzel unter die andere gehängt wird.

Zwei Optimierungen machen sie schnell genug, um aus der Komplexitätsanalyse zu verschwinden. Union by Rank hängt stets den flacheren Baum unter den höheren und verhindert so, dass die Struktur zu einer Kette entartet. Pfadkompression richtet jeden bei einem find besuchten Knoten direkt auf die Wurzel aus, sodass wiederholte Abfragen im Lauf des Algorithmus billiger werden.

Mit beidem kostet eine Folge von m Operationen auf n Elementen O(m α(n)), wobei α die inverse Ackermannfunktion ist. Sie wächst so langsam, dass sie für jede Eingabe, die in das beobachtbare Universum passt, unter 5 bleibt. Die Union-Find-Arbeit in Kruskal ist damit praktisch linear in der Kantenzahl.

6. Implementierung und Pseudocode

Da Union-Find die Schwierigkeit trägt, ist der Algorithmus selbst kurz.

function Kruskal(V, edges):
    sortiere edges aufsteigend nach Gewicht
    makeSet(v) für jeden Knoten v      // V einelementige Fragmente
    mst = []

    for jede Kante (u, v, w) in sortierter Reihenfolge:
        if find(u) != find(v):         // verschiedene Fragmente
            union(u, v)
            mst.append((u, v, w))
            if size(mst) == V - 1:     // vorzeitiges Ende: Baum vollständig
                break

    return mst

Zwei Details sind erklärungsbedürftig. Das break ist für die Korrektheit nicht nötig, da jede spätere Kante ohnehin verworfen würde, überspringt bei einem dichten Graphen jedoch den Großteil der Liste. Und das break ganz wegzulassen ist kein Fehler: Genau das macht daraus einen Algorithmus für minimale Spannwälder, wie unten beschrieben.

Der Vergleich find(u) != find(v) ist die einzige Stelle, an der Zyklen überhaupt betrachtet werden. Nirgends findet eine explizite Zyklenerkennung statt, und darin liegt die Eleganz des Ansatzes: Die Buchführung über den Zusammenhang erledigt das implizit.

7. Zeit- und Speicherkomplexität

• Sortieren: O(E log E). Das dominiert alles Übrige. Da E < V2 gilt, ist log E < 2 log V, weshalb die Schranke gleichwertig als O(E log V) geschrieben wird.
• Union-Find: O(E α(V)). Höchstens zwei find-Aufrufe und ein union je Kante. Praktisch linear.
• Insgesamt: O(E log E). Die Sortierung und sonst nichts.
• Speicher: O(V + E). Die Eltern- und Rangfelder sind O(V), die Kantenliste selbst O(E).

Da sich die Kosten an einer Stelle bündeln, setzen alle sinnvollen Optimierungen an der Sortierung an. Kommen die Kanten bereits sortiert an, oder sind die Gewichte kleine ganze Zahlen, die ein Radix- oder Zählsortieren erlauben, sinkt der gesamte Algorithmus auf O(E α(V)), also nahezu linear. Auch eine Teilsortierung oder ein lazy aufgebauter Heap hilft: Die volle Ordnung braucht man selten, denn der Algorithmus endet meist lange vor den schwersten Kanten.

8. Kruskal gegen Prim

Beide sind gierig, beide werden durch dasselbe Satzpaar gerechtfertigt, und bei paarweise verschiedenen Gewichten liefern beide denselben Baum. Die praktischen Unterschiede folgen daraus, was jeder zusammenhängend hält.

                 Kruskal                      Prim
Struktur         Wald aus Fragmenten          ein wachsender Baum
getrieben von    sortierter Kantenliste       Prioritaetswarteschlange
braucht          Union-Find                   Heap (oder V x V Suche)
Kosten           O(E log E)                   O(E log V), dicht O(V^2)
gut bei          duennen Graphen              dichten Graphen
unzusammenhaeng. liefert Spannwald            spannt nur eine Komponente

Die Faustregel ist die Dichte. Bei einem dünn besetzten Graphen ist E klein, die Sortierung billig, und Kruskal gewinnt. Bei einem dichten Graphen, in dem E sich V2 nähert, kostet das Sortieren von rund V2 Kanten O(V2 log V), während Prim mit Adjazenzmatrix in glatten O(V2) läuft und die Führung übernimmt.

9. Praxishinweise und typische Fallstricke

Spannwälder und unzusammenhängende Graphen

Hier hat Kruskal einen echten strukturellen Vorteil. Lassen Sie ihn auf einem nicht zusammenhängenden Graphen laufen, so erreicht er schlicht nie V - 1 aufgenommene Kanten. Er arbeitet die Kantenliste ab, und was bleibt, ist ein minimaler Spannwald: der minimale Spannbaum jeder Zusammenhangskomponente, in einem Durchlauf und ohne Sonderbehandlung berechnet.

Prim kann das von einem einzigen Start aus nicht. An einem Knoten gestartet, spannt er dessen Komponente auf und hält an, wobei er stillschweigend einen Baum zurückgibt, der gültig aussieht, aber nur einen Teil des Graphen abdeckt. Den Rest zu erfassen heißt, den Fehlbetrag zu erkennen und je Komponente einmal von einem unbesuchten Knoten aus neu zu starten. Die Zählung ist zugleich die Diagnose: Endet Kruskal mit V - 1 Kanten, war der Graph zusammenhängend; endet er mit V - k, hatte der Graph k Komponenten.

Maximaler Spannbaum

Sortieren Sie absteigend statt aufsteigend, und jede Zeile des Algorithmus gilt weiterhin. Die Zykluseigenschaft schlägt in ein Schnitteigenschaftsargument auf negierten Gewichten um, und Sie erhalten den schwersten Spannbaum. Die Gewichte zu negieren und den Algorithmus unverändert laufen zu lassen funktioniert ebenso gut.

Reverse-Delete

Das Spiegelbild von Kruskal: Sortieren Sie die Kanten von der schwersten zur leichtesten und löschen Sie jede, sofern ihr Löschen den Graphen nicht trennt. Gerechtfertigt wird es durch dieselbe, rückwärts gelesene Zykluseigenschaft, und es liefert denselben Baum. Es wird selten verwendet, weil der Zusammenhangstest nach jeder Löschung weit teurer ist als eine Union-Find-Abfrage.

Gleiche Gewichte

Teilen sich mehrere Kanten ein Gewicht, kann der Graph mehr als einen minimalen Spannbaum besitzen, und welchen Sie erhalten, hängt davon ab, wie Ihre Sortierung Gleichstände ordnet. Das obige Beispiel enthält einen solchen Gleichstand: B-C und D-E wiegen beide 2. Alle daraus entstehenden Bäume sind gleich optimal, weshalb jeder Test, der gegen eine feste Kantenliste vergleicht, brüchig ist. Vergleichen Sie stattdessen das Gesamtgewicht.

Schleifen und Mehrfachkanten

Eine Schleife scheitert stets am Test find(u) != find(v) und wird automatisch verworfen, braucht also keine Sonderbehandlung. Unter Mehrfachkanten wird die günstigste zuerst erreicht und aufgenommen, der Rest anschließend als Zyklus verworfen. Kruskal ist gegenüber unsauberen Eingaben ungewöhnlich nachsichtig.

10. Anwendungen in der Praxis

Netz- und Infrastrukturplanung

Die ursprüngliche Motivation: eine feste Menge von Standorten mit möglichst wenig Kabel, Rohr oder Gleis verbinden. Kruskals kantenzentrierte Sicht passt natürlich, wenn die Eingabe ohnehin als Liste von Kandidatenverbindungen mit Kosten vorliegt, was bei solchen Daten meist der Fall ist.

Hierarchisches Clustering

Lassen Sie Kruskal laufen und halten Sie die Reihenfolge fest, in der Fragmente verschmelzen, so haben Sie agglomeratives Single-Linkage-Clustering durchgeführt. Die Folge der Verschmelzungen ist genau das Dendrogramm, und ein vorzeitiger Stopp bei V - k Kanten hinterlässt exakt k Cluster. Diese Äquivalenz erklärt, warum minimale Spannbäume im unüberwachten Lernen so häufig auftauchen.

Bildsegmentierung

Behandelt man Pixel als Knoten und Intensitätsunterschiede als Kantengewichte, ist der Segmentierungsalgorithmus von Felzenszwalb und Huttenlocher im Kern Kruskal mit einem Verschmelzungskriterium, das die interne Variation eines Fragments gegen das Kantengewicht abwägt.

Schaltungs- und Layoutentwurf

Die Gesamtleitungslänge zwischen festen Anschlusspunkten zu minimieren ist ein Spannbaumproblem, und die Kantenliste möglicher Leitungswege hat ein Router ohnehin zur Hand.

11. Wissenschaftliche Quellen und Geschichte

Anders als der Algorithmus von Prim, der mindestens dreimal unabhängig entdeckt wurde, hat dieser eine klare Zuschreibung.

• Joseph B. Kruskal (1956) veröffentlichte ihn in einer dreiseitigen Notiz, On the shortest spanning subtree of a graph and the traveling salesman problem, in den Proceedings of the American Mathematical Society. Die Arbeit erschien ein Jahr vor der von Prim und dreißig Jahre nach der von Borůvka.
• Otakar Borůvka (1926) hatte das Problem des minimalen Spannbaums Jahrzehnte früher gestellt und gelöst, im Zuge der Elektrifizierung des ländlichen Mährens.
• Robert Tarjan (1975) bewies die nahezu konstante amortisierte Schranke für Union-Find mit Union by Rank und Pfadkompression, was den nicht sortierenden Teil der Kosten von Kruskal auf O(E α(V)) festlegt.

Die vollständige Zuschreibungsgeschichte des Problems findet sich bei Graham und Hell. Für strenge Beweise der Schnitt- und der Zykluseigenschaft sowie beider Algorithmen ist Cormen, Leiserson, Rivest und Stein, Introduction to Algorithms, im Kapitel über minimale Spannbäume das Standardwerk. Die vollständigen Quellenangaben finden sich am Ende dieses Artikels.