Operations Research

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.

Kruskal-Algorithmus und minimale Spannbäume
direkt ins Video springen
Kruskal Algorithmus zum Ermitteln minimaler Spannbäume

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.

Kruskal Algorithmus: Kanten sortieren und aktuell kürzeste Kante hinzufügen
direkt ins Video springen
Vorgehen beim Kruskal Algorithmus

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.

Kantengewichte sortieren
direkt ins Video springen
Kruskal Algorithmus: Kanten nach Gewichten sortieren

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.

Vorgehen beim Kruskal-Algorithmus: aktuell günstigste Kante hinzufügen
direkt ins Video springen
Aktuell kostengünstigste Kante einfügen

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.

Kruskal Algorithmus: Keine Zyklen bilden
direkt ins Video springen
Vorgehen beim Kruskal Algorithmus: Keine Kanten einfügen die Kreise bilden

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.

Kruskal Algorithmus und Minimaler Spannbaum
direkt ins Video springen
Minimalen Spannbaum mittels des Kruskal Algorithmus bilden

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.


Andere Nutzer halten diese Inhalte aus dem Bereich „Operations Research“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.