Der Kruskal-Algorithmus verständlich erklärt

Wer mehrere Orte mit einer Leitung verbinden will, sucht das Netz, das alle erreicht und dabei möglichst wenig kostet. Der Kruskal-Algorithmus baut es Schritt für Schritt auf und nimmt immer die billigste Verbindung, die keine Schleife schließt. Diese Seite erklärt zuerst ohne Formeln, warum dieses Vorgehen hier das Beste liefert und was das Netz trotzdem nicht leistet, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Netz, das alle erreicht und möglichst wenig kostet

Stellen Sie sich eine Handelskette vor, die Glasfaser zu allen ihren Filialen verlegen will. Es gibt ein Depot, von dem aus eingespeist wird. Zwischen vielen Paaren von Orten könnte man einen Leitungsabschnitt bauen, eine Trasse, jede mit eigenen Baukosten, die vor allem von Länge und Gelände abhängen. Gesucht sind die Trassen, die alle Orte verbinden und zusammen am wenigsten kosten.

Enthält ein Netz irgendwo eine Schleife, also Trassen, die im Kreis zum Ausgangsort zurückführen, ist eine Trasse davon überflüssig. Nimmt man sie weg, bleiben alle Orte verbunden, denn die Daten laufen um die Schleife herum. Das Netz wird billiger, solange jede Trasse etwas kostet. Das billigste hat also keine Schleife. Fachleute nennen sie einen Kreis.

Ein Netz ohne Schleife, das alle Orte verbindet, verzweigt sich wie ein Baum, dessen Äste sich nie wieder treffen. Es hat immer eine Trasse weniger, als es Orte gibt. Fachleute nennen es einen Spannbaum, weil es alle Orte umspannt; der billigste heißt minimaler Spannbaum. Den baut der Kruskal-Algorithmus, eine nach ihrem Erfinder benannte Rechenvorschrift.

Die Regel: die billigste Trasse, die keine Schleife schließt

Zuerst schreibt man alle denkbaren Trassen auf, sortiert vom billigsten zum teuersten. Dann geht man die Liste von oben nach unten durch und fragt bei jeder Trasse: Sind ihre beiden Enden schon über gebaute Trassen verbunden? Wenn nein, wird sie gebaut. Wenn ja, würde sie eine Schleife schließen, und sie wird verworfen.

Ein Beispiel mit drei Orten, Hafen, Werk und Lager. Die billigste Trasse führt vom Hafen zum Werk, die zweitbilligste vom Werk zum Lager, die dritte vom Hafen zum Lager. Die ersten beiden werden gebaut. Bei der dritten sind Hafen und Lager schon über das Werk verbunden. Sie würde eine Schleife schließen und fällt weg.

Das Netz wächst nicht von einem Punkt aus. Zu Beginn steht jeder Ort für sich. Dann entstehen kleine Inseln aus verbundenen Orten, die zusammenwachsen. Ein Merkzettel hält für jeden Ort fest, zu welcher Insel er gehört, damit die Frage nach der Verbindung schnell beantwortet ist. Sobald eine Trasse weniger gebaut ist, als es Orte gibt, sind alle verbunden, und das Verfahren hört auf.

Warum die Gier hier stimmt

Ein Verfahren, das in jedem Schritt die gerade beste Möglichkeit nimmt und nie zurückgeht, heißt gierig. Meist ist das riskant: Wer an jeder Kreuzung die nächste kürzeste Straße nimmt, kommt nicht immer auf dem besten Gesamtweg an. Beim billigsten Netz ist die Gier dagegen kein Fehler, solange nur die Baukosten zählen.

Teilen Sie die Orte irgendwie in zwei Gruppen auf, etwa die westlichen und die östlichen. Jedes Netz, das alle verbindet, muss irgendwo über die Grenze zwischen den Gruppen führen. Angenommen, ein Netz nutzt dafür eine teure Verbindung, obwohl eine billigere über dieselbe Grenze möglich wäre. Baut man die billigere dazu, entsteht eine Schleife. Sie quert die Grenze zweimal, enthält also noch eine zweite Trasse über die Grenze. Diese zweite ist nicht billiger als die neue, also tauscht man sie gegen die neue aus. Das Netz verbindet weiter alle Orte, hat keine Schleife und ist nicht teurer. Die billigste Verbindung über eine Grenze ist deshalb nie ein Fehler.

Für Kruskal heißt das: Jede Insel gegen alle übrigen Orte ist so eine Grenze. Führt eine Trasse aus einer Insel hinaus und wird gebaut, ist sie die billigste über diese Grenze. Billigere stehen weiter oben in der Liste und sind schon entschieden, und die verworfenen lagen innerhalb von Inseln. Das trägt, solange der Preis jeder Trasse feststeht, ohne Rabatt dafür, dass man andere mitbaut.

Was das billigste Netz nicht verspricht

Das billigste Netz ist eine reine Kostenantwort. Es fragt nicht, wie lang der Weg von einer Filiale zum Depot im Netz ist. In der Demo zu dieser Seite, einem Programm zum Ausprobieren, ist dieser Weg bei vielen Filialen länger als der kürzeste mögliche Weg, und das Netz mit den kürzesten Wegen kostet dort mehr. Wer Baukosten und Weglänge zugleich begrenzen will, braucht ein anderes Verfahren.

Außerdem ist das billigste Netz nicht stabil. In der Demo kann schon eine kleine Änderung aller Trassenkosten ein anderes Netz ergeben: bei den kleinsten Beispielen nie, bei den größten in den meisten Versuchen. Haben mehrere Trassen genau dieselben Kosten, sind mehrere gleich billige Netze möglich. Die Gesamtkosten sind dann gleich, das Netz nicht.

Wie ernst ist das Modell zu nehmen?

Die Demo rechnet mit erzeugten Beispielen: Punkte auf einer Fläche, Baukosten nach Abstand plus ein zufälliger Aufschlag fürs Gelände, ohne echtes Straßennetz.

Was Sie mitnehmen: Zählen nur die Baukosten, und kostet jede Trasse für sich, dann ist der billigste Spannbaum die richtige Antwort. Fragen Sie Ihren Planer, wie lang die Wege zum Depot im Netz werden und ob bei leicht geänderten Kosten ein anderes Netz herauskäme. Sind beide Fragen wichtig, braucht es ein anderes Verfahren. Woran Sie es im eigenen Betrieb erkennen: Zu manchen Orten ist der Weg über das Netz länger als nötig, und die Planer wissen nicht, warum. Ein Baum hat zudem keine Ersatzwege: Fällt eine Trasse aus, sind Orte abgeschnitten. Das ist eine eigene Einschätzung, keine Messung der Demo; wo Ausfälle teuer sind, wird man in der Praxis Schleifen bewusst zulassen.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Problem: zusammenhängender Graph \(G=(V,E)\) mit Kantenkosten \(w_e\); gesucht ist ein Spannbaum \(T \subseteq E\) (azyklisch, zusammenhängend, \(\lvert T\rvert = \lvert V\rvert-1\)) mit minimalen Gesamtkosten.
• Instanz: Depot (Knoten 0, am linken Rand) und n Filialen im Quadrat. Die Kantenkosten sind der euklidische Abstand mal ein Geländefaktor in [1, 1 + Zuschlag], der nur vom Knotenpaar und vom Zufalls-Seed abhängt; wer k ändert, streicht Kanten, ändert aber keine Kosten. Der Kandidatengraph ist vollständig oder besteht aus den k nächsten Nachbarn (Zusammenhang garantiert). „Kosten runden“ erzeugt bewusst viele Gleichstände. Dazu zwei feste Instanzen: ein Lehrbuchbeispiel und eine Ketten-Instanz für die Union-Find-Falle.
• Verfahren: Sortieren nach (Kosten, Tie-Rang), Annahme oder Verwerfen per Union-Find in vier Stufen (naiv, Pfadhalbierung, Vereinigung nach Rang, beides), Stopp nach \(\lvert V\rvert-1\) angenommenen Kanten. Zusätzlich Filter-Kruskal: quicksort-artiges Teilen am Median dreier Kanten, die leichte Hälfte zuerst, aus der schweren vor dem Sortieren alle Kanten innerhalb einer Komponente entfernt. Referenzen: ein unabhängiges Prim und der Kürzeste-Wege-Baum (Dijkstra) ab dem Depot.
• Auswertung: Ersparnis gegen Einzelanbindung, Umweg-Faktor, Aufschlag des Kürzeste-Wege-Baums, betrachtete und sortierte Kanten, Zeigerschritte, Instabilität (±1 % Rauschen, 20 Versuche) und die exakte Anzahl aller MSTs (Produkt über die Kostenklassen der Zahl der Spannbäume im Klassen-Multigraphen, Determinante per Bareiss-Verfahren).

Die Formeln

Zu minimieren sind die Gesamtkosten des Spannbaums.

\[\sum_{e\in T} w_e\]

Zwei Eigenschaften machen die Gier korrekt. Schnitt-Eigenschaft: Für jeden Schnitt \((S, V\setminus S)\) gehört eine billigste Kante über den Schnitt zu einem MST (bei eindeutig billigster Kante zu jedem). Kreis-Eigenschaft: Eine Kante, die auf einem Kreis strikt teurer ist als alle anderen Kanten dieses Kreises, gehört zu keinem MST. Kruskal sortiert \(E\) nach (Kosten, Tie-Rang) und nimmt für jede Kante \(\{u,v\}\) die Kante an und vereinigt die beiden Komponenten, falls

\[\text{find}(u) \ne \text{find}(v)\]

gilt. Dann ist die Kante die billigste noch nicht entschiedene und verbindet zwei Komponenten, also ist sie nach der Schnitt-Eigenschaft (Schnitt: die Komponente gegen den Rest) sicher. Verworfene Kanten liegen innerhalb einer Komponente und schließen einen Kreis. Die Laufzeit ist \(O(m \log m)\) für das Sortieren plus \(O(m\,\alpha(m,n))\) für Union-Find mit Rang und Pfadkompression (in der Demo als Pfadhalbierung umgesetzt); \(\alpha\) ist die inverse Ackermann-Funktion. Als Kontrast misst die Demo den Umweg-Faktor einer Filiale \(v\), mit \(d_T\) als Weglänge im Baum und \(d_G\) als kürzestem Weg im Kandidatengraphen:

\[s(v) = d_T(\text{Depot}, v) / d_G(\text{Depot}, v) \ge 1\]

Die Zahl aller MSTs entsteht nach Kostenklassen gruppiert als Produkt, über alle Klassen, der Zahl der Spannbäume im Multigraphen der Klasse-Kanten zwischen den bis dahin entstandenen Komponenten; der Matrix-Tree-Satz liefert sie als Determinante eines Kofaktors der Laplace-Matrix.

Befunde

Alle Zahlen stammen aus der README der Demo, und ihre Aussagen sind dort als Tests hinterlegt. Soweit nicht anders angegeben, gelten sie für 30 Filialen plus Depot, k = 6 nächste Nachbarn, Geländezuschlag 0,3 und exakte Kosten; Mediane über 5 feste Instanzen (Zufalls-Seeds 100000–100004), die Rechnung ist vollständig deterministisch.

Frage	Befund
Ist Kruskal optimal?	Ja, direkt geprüft: Schnitt- und Kreis-Eigenschaft für jede Kante, Brute-Force-Aufzählung aller Spannbäume (kleine Graphen mit 5 Knoten), scipy und ein unabhängiges Prim. Die Kosten sind immer gleich, bei paarweise verschiedenen Kosten kommt derselbe Baum heraus.
Wie läuft das Lehrbuchbeispiel?	5 Knoten, 7 Kanten: Kosten 15. Die Kante A–D (5) schließt einen Kreis und wird verworfen; 5 von 7 Kanten werden betrachtet.
Wie viel spart der Baum gegen Einzelleitungen?	73,7 % bei 30 Filialen (jede Filiale bekommt ihre eigene Leitung auf dem kürzesten Weg zum Depot). Bei n = 10/20/40/80/160 Filialen: 52,1/67,5/77,6/86,2/90,4 %. Der Geländezuschlag ändert das kaum: 74,3/73,8/73,7/73,8/73,8/73,8 % bei 0/0,2/0,4/0,6/0,8/1,0 (Spanne 0,6 Prozentpunkte).
Ist der Baum auch kurz?	Nein: Der Umweg-Faktor (Weg im Baum / kürzester Weg) ist 1,37 im Median und 3,32 im Maximum; bei n = 160 ist das Maximum 7,95. Der Kürzeste-Wege-Baum kostet 47,2 % mehr (k = 3: 24,7 %, vollständiger Graph: 137,7 %).
Wie viele Kanten muss Kruskal ansehen?	Der Anteil betrachteter Kanten bei k = 3/4/6/10/20/vollständig ist 88,7/79,0/62,9/42,4/22,2/17,9 %: je dichter der Graph, desto weniger. Filter-Kruskal sortiert dabei nur 78,1/71,6/41,0/27,3/13,5/13,3 %.
Was bringt Union-Find?	Zeigerschritte auf Zufallsinstanzen (vollständiger Graph) bei n = 20/40/80/160: naiv 151/778/1237/4001, Pfadhalbierung 69/282/438/945, nach Rang 105/407/753/1889, Rang + Pfadhalbierung 66/250/385/881. Auf der Ketten-Instanz (n = 20/40/80/160): naiv 170/740/3080/12560 (quadratisch, Tiefe n − 1), Pfadhalbierung 17/37/77/157, nach Rang 51/111/231/471.
Ist der Baum eindeutig?	Nur bei paarweise verschiedenen Kosten. Mit gerundeten Kosten gibt es bei n = 30 (Zufalls-Seed 35) 4 kostengleiche Bäume, bei n = 100 vollständig gerundet 1536 (exakt per Matrix-Tree-Satz gezählt). Die Kosten hängen nie von der Tie-Reihenfolge ab.
Wie stabil ist der Baum?	±1 % Rauschen auf allen Kantenkosten ändert ihn in 30 % der Läufe; bei n = 10/20/40/80/160 in 0/0/30/60/70 %, mit gerundeten Kosten in 80 %.
Und eine einzelne Instanz?	Die Voreinstellung (30 Filialen, k = 6, Zufalls-Seed 35) hat Kosten 466,63, Ersparnis 72,4 %, 90 von 113 Kanten betrachtet, Umweg-Faktor 1,26 / 3,54, Kürzeste-Wege-Baum +57 % und Instabilität 35 %. Die einzelne Instanz weicht von den Medianen ab; belastbar sind die Mediane.

Grenzen

• Reine Kostenantwort: Der billigste Baum begrenzt weder Umwege noch Grade oder Kapazitäten. Wer das braucht, sucht andere Bäume (Grad-, Hop- oder Kapazitätsgrenzen); die Demo zeigt sie nicht.
• Nicht eindeutig, nicht stabil: Eindeutigkeit gilt nur bei paarweise verschiedenen Kosten. Die Instabilität misst ±1 % Rauschen in 20 Versuchen; sie hängt stark von der Größe ab (von 0 % bei 10 und 20 Filialen bis 70 % bei 160).
• Nur gegebene Knoten: Kruskal nimmt nur Kanten zwischen den gegebenen Orten. Zusätzliche Verzweigungspunkte (Steiner-Punkte) können das Netz kürzen, sind aber NP-schwer und nicht Teil der Demo.
• Synthetische Instanzen: Punkte im Quadrat, euklidische Kosten mit Zufallszuschlag, kein Straßennetz, keine Kapazitäten oder Richtungen. Andere Netzstrukturen wurden nicht gemessen; die Ketten-Instanz hat abstrakte Kosten, Ersparnis und Umwege sind dort ohne Bedeutung.
• Zähler, keine Laufzeiten: Die Union-Find-Befunde zählen Zeigerschritte. Dass die Pfadhalbierung allein fast alles herausholt (945 gegen 881 bei n = 160), gilt für diese Zufallsinstanzen; die Vereinigung nach Rang allein (1889) holt deutlich weniger heraus.
• Nicht umgesetzt: Die asymptotisch besseren Verfahren von Karger, Klein und Tarjan, von Chazelle sowie von Pettie und Ramachandran. Nach der README gewinnen in der Praxis (Filter-)Kruskal, Prim und Borůvka-Varianten auf GPUs.

Quellen

• Kruskal, J. B. (1956): On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7(1), 48–50.
• Tarjan, R. E. (1975): Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2), 215–225.
• Osipov, V., Sanders, P., & Singler, J. (2009): The Filter-Kruskal Minimum Spanning Tree Algorithm. ALENEX 2009, 52–61.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/kruskal-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo. Der Austauschgedanke im Einsteigerteil (billigere Kante dazunehmen, eine teurere Kante des entstehenden Kreises über den Schnitt entfernen) und die Voraussetzung, dass die Kosten jeder Kante nur von ihr selbst abhängen, sind Standardwissen der Theorie und stehen nicht in der README; die README belegt die Eigenschaften durch Tests.