Kruskal-Algorithmus

In diesem Kurstext behandeln wir den Algorithmus von Kruskal, welcher einen minimalen Spannbaum für ungerichtete,kantengewichtete und zusammenhängend endlichen Graphen ermittelt.

Der Kurskal-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.

Der Kruskal-Algorithmus wurde 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlicht und stammt von dem US-amerikanischen Mathematiker Joseph Kruskal (1928-2010), der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte.  

Beispiel: Kruskal Algorithmus

Zum besseren Verständnis betrachten wir als nächstes ein Beispiel zum Kruskal-Algorithmus.

Gegeben sei der folgende ungerichtete, gewichte und zusammenhängend endliche Graph:

Kruskal-Algorithmus

Das Vorgehen beim Kruskal-Algorithmus ist recht simple. Es werden in aufsteigender Reihenfolge (nach Kantengewichten) die Konten abgefahren. Dabei darf kein Kreis entstehen. Sind alle Kanten abgefahren, so endet der Algorithmus.

Wir beginnen beim Kruskal-Algorithmus mit der Kante, die das kleinste Kantengewicht aufweist. Sind mehrere Kanten mit demselben Gewicht gegeben, so erfolgt die Auswahl beliebig.

Kruskal-Algorithmus: Vorgehen (1)

Im obigen Bild beginnen wir damit die Kante mit dem kleinsten Gewicht auszuwählen. Wir haben hier die Möglichkeit die Kante GH oder die Kante CD mit dem Kantengewicht 1 auszwählen. Wir können hier eine beliebige Auswahl treffen und wählen die Kante GH und markieren diese grün. Um die Übersicht zu behalten, tragen wir die besuchten Knoten (hier: G und H) oben rechts neben dem Graphen ein.

Danach gehen wir zu Kante CD mit dem Kantengewicht 1 über, markieren diese Kante und fügen die Knoten C und D als besucht hinzu. 

Kruskal-Algorithmus: Vorgehen (2)

Die Kanten AC oder BD mit dem Gewicht 2 werden als nächstes betrachtet und bliebig zunächst die Kante AC ausgewählt und grün markiert. Der Knoten C ist bereits als besucht eingetragen, der Knoten A wird als besucht übernommen. Danach folgt die Kante BD und der Knoten B wird als besucht übernommen. 

Die Kanten mit dem Kantengewicht 3 sind als nächstes an der Reihe. Dort wählen wir beliebig die Kante FG aus und übernehmen F als besucht.

Kruskal-Algorithmus: Vorgehen (3)

Danach betrachten wir die Kante AB. Diese Kante dürfen wir nicht wählen, da diese Kante mit den zuvor gewählten Kanten einen Kreis bildet. 

Würden wir die Kante AB hinzufügen, so ergäbe sich der folgende Kreis: A-B-D-C-A. Wir markieren die Kante also rot, um aufzuzeigen, dass diese Kante nicht gewählt werden darf.

Die nächsten Kanten die betrachtet werden, sind diejenigen mit dem Kantengewicht 6. Die Kante AD darf nicht gewählt werden, weil sich sonst der Kreis A-C-D-A ergeben würde. Die Kante DE kann gewählt werden. Beide Knoten D und E sind bereits besucht, es wird also die Kante DE grün markiert und kein Knoten als besucht übernommen, da schon vorhanden.

Kruskal-Algorithmus: Vorgehen (4)

Wir betrachten als nächsten die Kante DG und markiere diese grün, da kein Kreis mit den bereits besuchten Kanten entsteht. Wir müssen nun auch keine Knoten mehr als besucht hinzufügen, da bereits alle acht Knoten besucht sind.

Es folgen die Kanten mit dem Gewicht 7. Alle drei Kanten FB, FD und EH bilden Kreise mit den bereits besuchten (grünen) Kanten. Demnach werden diese Kanten nicht im Spannbaum berücksichtigt und mit rot markiert.

Die Kante DH mit dem Gewicht 8 bildet ebenfalls einen Kreis mit den bereits besuchten Kanten und bleibt demnach unberücksichtigt im Spannbaum.

Kruskal-Algorithmus: Ergebnis

Die letzte zu betrachtende Kante ist die Kante CF mit dem Gewicht 9. Diese Kante bleibt unberücksichtigt, da ansonsten ein Kreis entstehen würde (C-F-G-D-C).

Wir haben alle Kanten abgefahren, demnach ist der Kruskal-Algorithmus terminiert, d.h. er ist beendet. Der minimale Spannbaum ergibt sich aus den grün markierten Kanten:

Kruskal-Algorithmus: Minimaler Spannbaum