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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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.
Kruskal Algorithmus — häufigste Fragen
(ausklappen)
Kruskal Algorithmus — häufigste Fragen
(ausklappen)-
Was ist ein Spannbaum?Ein Spannbaum ist ein Teilgraph eines zusammenhängenden Graphen, der alle Knoten enthält und sie so verbindet, dass kein Kreis entsteht. Dadurch bleiben nur so viele Kanten übrig, wie zum Verbinden nötig sind, typischerweise genau eine Kante weniger als Knoten.
-
Ist der minimale Spannbaum eindeutig?Der minimale Spannbaum ist nicht immer eindeutig, weil es in einem Graphen mehrere verschiedene Spannbäume mit derselben minimalen Gesamtkosten-Summe geben kann. Eindeutig ist er nur dann sicher, wenn die Kantengewichte so verteilt sind, dass es keine „Gleichstände“ bei entscheidenden Kanten gibt.
-
Wie erkennt Kruskals Algorithmus Zyklen?Zyklen erkennt der Kruskal-Algorithmus, indem man vor dem Hinzufügen einer Kante prüft, ob ihre beiden Endknoten im aktuellen Teilgraphen schon über vorhandene Kanten miteinander verbunden sind. Falls sie bereits verbunden sind, würde die neue Kante einen Kreis schließen und wird übersprungen.
-
Wann kann man beim Kruskal-Algorithmus aufhören?Beim Kruskal-Algorithmus kann man aufhören, sobald der aktuelle Teilgraph alle Knoten verbindet und damit ein Spannbaum ist. Praktisch erkennt man das daran, dass der Spannbaum bei
Knoten genau 
Kanten hat und jede weitere zulässige Kante nur noch einen Kreis erzeugen würde.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Algorithmen verstehen
Der Kruskal-Algorithmus gehört zu den grundlegenden Algorithmen der Informatik und ist ein typisches Verfahren aus der Graphentheorie. Wer sich mit Algorithmen beschäftigt, ordnet Abläufe in klare Schritte ein und vergleicht verschiedene Lösungswege für ein Problem. So wird auch verständlich, warum ein Greedy-Algorithmus an jeder Stelle die gerade beste Wahl trifft und trotzdem zu einer sinnvollen Lösung führt. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.