Kruskal Algorithmus
Du hast einen Graphen mit vielen Kanten vorliegen und willst ihn einfacher darstellen? In diesem Beitrag zeigen wir dir den Ablauf des Kruskal-Algorithmus an einem Beispiel.
Inhaltsübersicht
Algorithmus von Kruskal – Minimaler Spannbaum
Der Algorithmus von Kruskal ist ein Greedy-Algorithmus , der für zusammenhängende , gewichtete Graphen den minimalen Spannbaum ermittelt.
Ein minimaler Spannbaum ist der Teilgraph eines Graphen, der mindestens nötig ist, um alle Knoten möglichst kostengünstig miteinander zu verbinden.
Falls du nicht mehr genau weißt, was ein Greedy-Algorithmus ist, oder du das gleiche Beispiel mit dem Prim-Algorithmus sehen willst, dann schau dir einfach unsere Videos dazu an.
Ablauf des Kruskal Algorithmus
Um den minimalen Spannbaum zu ermitteln, sortiert der Algorithmus zuerst alle Kanten aufsteigend nach ihren Kantengewichten .
Du erstellst dir einen neuen Graphen, der alle Knoten des alten Graphen, jedoch noch keine Kanten enthält. Nach und nach werden jetzt die aufsteigend sortierten Kanten hinzugefügt. Somit wird Knoten für Knoten zum Graphen hinzugezogen. Da hierbei immer die Kante, die aktuell am kürzesten ist, hinzugefügt wird, gehört der Kruskal Algorithmus zu den Greedy-Algorithmen. Aber Achtung: der Algorithmus fügt nur Kanten hinzu, die keine Kreise bilden.
Ablauf anhand von Beispiel
Lass uns das doch einfach mal an einem Beispiel versuchen.
Wir sortieren als erstes die Kanten nach ihren Kosten. Die kürzeste ist hierbei die Kante CE mit Kosten von 9.
Jetzt erstellen wir einen neuen Graphen für unseren minimalen Spannbaum. Wir übernehmen alle Knoten aus dem Alten.
Nun können wir auch schon mit dem Einfügen der Kanten beginnen. Noch haben wir keine Kanten im Graphen. Daher kann also kein Kreis entstehen und wir können unsere günstigste Kante CE einfach einfügen.
Auch unsere nächst günstige Kante AD erzeugt keinen Kreis und wir fügen sie hinzu.
Wir erweitern den Graphen um weitere Kanten, bis wir auf unser erstes Problem stoßen: EG und BC haben die gleiche Länge. Hierbei kannst du dir einfach eine der beiden Kanten aussuchen.
Wählen wir die Kante EG aus. Wie du sehen kannst, würde beim Einfügen von EG allerdings ein Kreis entstehen.
Also überspringen wir diese und fahren mit BC fort. Wenn wir versuchen BC einzufügen, entsteht ebenfalls ein Kreis, also überspringen wir auch BC.
Wir fügen unsere nächste Kante ein, nämlich DF mit Kosten von 17.
Sicher fällt dir auf, dass jetzt alle Knoten in unserem minimalen Spannbaum enthalten sind. Da alle Kanten, die wir jetzt noch hinzufügen können, Kreise ergeben würden, sind wir fertig.
Super! Jetzt kannst du mit einem einfachen Schema einen minimalen Spannbaum aus einem Graphen konstruieren.
Unterschied zwischen Prim und Kruskal Algorithmus
Der Algorithmus von Prim liefert, genau wie der Algorithmus von Kruskal einen minimalen Spannbaum zu einem Graphen.
Der Unterschied liegt in der Funktionsweise: Der Kruskal-Algorithmus startet mit allen Knoten ohne Kanten und fügt nacheinander die global günstigsten Kanten ein. Der Algorithmus von Prim hingegen startet mit einem Knoten und fügt immer die günstigste Kante, die vom aktuellen Teilgraph erreichbar ist, hinzu.
Pseudocode Kruskal Algorithmus
Eine mögliche Implementierung des Kruskal-Algorithmus in Pseudocode könnte in etwa so aussehen:
V = Knoten
E = Kanten
MST = neue Kanten (zu Beginn leer)
sortiere Kanten aufsteigend
für jede Kante e in E:
entferne e aus E
wenn MST mit e keine Kreise enthält:
Füge e zu MST hinzu
Der Graph G = (V, MST) ist ein minimaler Spannbaum des Ausgangsgraphen.