Kruskal-Algorithmus

Der Kruskal-Algorithmus stammt vom US-amerikanischen Mathematiker und Statistiker Joseph Bernard Kruskal. Mit diesem Algorithmus lassen sich minimale Spannbäume von ungerichteten Graphen berechnen. Dafür muss der Graph aber nicht nur ungerichtet sein, sondern auch zusammenhängend, kantengewichtet und endlich sein.

Der Algorithmus ist relativ simpel. Man wählt aus den noch nicht gewählten Kanten immer die kürzeste Kante unter Berücksichtigung das sie mit den schon gewählten Kanten keinen Kreis ergibt. Dies führt man so lange aus, bis man einen minimalen Spannbaum erhalten hat. Anbei ein Beispiel wie sich der Baum langsam aufbaut.

Kruskal-Algorithmus Beispiel

Man gehe von folgenden Graph aus:

Beispiel Graph für Kruskal-Algorithmus

Nun wählt man die Kante mit dem geringsten Wert. Diese wäre im Beispiel die Kante zwischen Knoten B und Knoten E mit dem Wert 2. Da diese auf jeden Fall keinen Kreis bilden können, kann man sie nun zum Baum hinzufügen. Dieser sieht damit nach Schritt 1 folgendermaßen aus:

Erster Schritt im Kruskal-Algorithmus

Nun wählt man in den verbliebenen Kanten wieder die Kante mit dem geringsten Wert aus. Das wäre in diesem Fall entweder die Kante zwischen B und C oder zwischen E und D, da sie beide den Wert 3 aufweisen. Da keine Kante mit der Kante zwischen B und E einen Kreis schließen würde, kann man beide Kanten nehmen. Da man je Schritt aber nur eine Kante auswählen kann, muss man sich nun für eine Kante entscheiden. Diese Wahl ist willkürlich, ich habe mich in diesem Fall für die Kante zwischen E und D entschieden. Damit sieht der Baum nun folgendermaßen aus:

Zweiter Schritt im Kruskal-Algorithmus

Wie schon erwähnt, entsteht auch nicht mit der Aufnahme von Kante B zu C ein Kreis, demnach wird sie nun in Schritt 3 zum Baum hinzugefügt:

Dritter Schritt im Kruskal-Algorithmus

Die nächste Kante die zum Baum hinzugefügt werden darf ist die Kante zwischen B und F da sie mit ihren Wert von 4 kleiner als 5, 7 und 9 ist und darüber hinaus kein Kreis schließt.

Vierter Schritt im Kruskal-Algorithmus

Im fünften Schritt passiert nun genau das, was es zu vermeiden gilt. Die kleinste Kante ist die Kante zwischen F und E mit dem Wert 5. Würde man diese Kante aber nun hinzufügen, dann würde sich ein Kreis zwischen den Knoten B, E und F schließen. Dementsprechend wird die Kante nicht hinzugefügt, sondern verworfen. Es bleibt alles beim Alten:

Fünfter Schritt im Kruskal-Algorithmus

Auch im sechsten Schritt würde mit der Hinzunahme der Kante C - D ein Kreis zwischen B, C, D und E geschlossen werden. Dementsprechend kommt auch in Schritt 6 keine neue Kante hinzu:

Sechster Schritt im Kruskal-Algorithmus

Zum Schluss bleibt nur noch die Kante zwischen A und B mit Wert 9 übrig. Da sie kein Kreis bildet, kann sie hinzugefügt werden:

Siebter Schritt im Kruskal-Algorithmus

Damit wäre der minimale Spannbaum mit dem Kruskal-Algorithmus schon aufgestellt, da es keine weitere Kanten mehr zum Hinzufügen gibt.