Kruskal-Algorithmus
Kruskal-Algorithmus Definition
Der Kruskal-Algorithmus löst – wie der Prim-Algorithmus – dieses Problem:
Ausgangspunkt
Ausgangspunkt ist ein ungerichteter, zusammenhängender, kantengewichteter Graph; dieser besteht beispielsweise aus Städten (Knoten), die durch in beide Richtungen befahrbare Straßen (ungerichtete Kanten) verbunden sind und diese Kanten sind mit Entfernungen oder Kosten gewichtet (kleinere Entfernungen oder Kosten sind besser).
Ziel / Ergebnis: minimaler Spannbaum
Der Kruskal-Algorithmus sucht dann den minimalen Spannbaum, also das Verbindungsnetz, mit dem alle Knoten (Städte) zu insgesamt minimalen Kosten besucht werden können.
Alternative Begriffe: Algorithmus von Kruskal.
Beispiel
Beispiel: Kruskal-Algorithmus anwenden
Wir greifen das Beispiel des Prim-Algorithmus auf:
Der Graph umfasst die 4 Knoten bzw. Städte Aachen, Berlin, Celle und Dortmund, die im folgenden mit ihren Anfangsbuchstaben abgekürzt werden.
Die Städte sind durch folgende Bahnstrecken oder Autobahnen (Kanten) mit hier fiktiven km -Angaben verbunden:
A – B: 200 km
A - C: 300 km
B - C: 250 km
B - D: 400 km
C - D: 350 km
Was ist der minimale Spannbaum, also das Verbindungsnetz, mit dem alle 4 Knoten zu minimalen Kosten besucht werden können?
Der Kruskal-Algorithmus löst das in mehreren Iterationen (Durchgängen) so:
Beginn
Man beginnt mit der kleinsten Kante (der Kante, mit dem geringsten Gewicht); das ist A - B mit 200 km.
Iterationen
Anschließend die nächstkleinste Kante: B - C mit 250 km.
Anschließend die nächstkleinste Kante: A - C mit 300 km. Diese wählen wir allerdings nicht, da sonst ein geschlossener Kreis entstünde aus den Knoten A, B und C.
Nächstkleinste Kante: C - D mit 350 km.
Ende
Alle Knoten A, B, C und D sind einbezogen, der Algorithmus ist beendet.
Das gesamte Kantengewicht ist: 200 km (A - B) + 250 km (B - C) + 350 km (C - D) = 800 km.
Der Prim-Algorithmus hatte auf einem anderen Weg denselben minimalen Spannbaum gefunden.
Zusammengefasst
Immer die jeweils kleinste Kante wählen (gibt es mehrere gleichkleine, kann man aus diesen frei wählen).
Kanten, die zu einem geschlossenen Kreis bzw. Zyklus führen würden, dürfen nicht gewählt werden.