Der minimale Spannbaum eines Graphen – was das ist, und wie man diesen mit dem Algorithmus von Prim erstellt, zeigen wir dir in diesem Beitrag!
Inhaltsübersicht
Algorithmus von Prim – minimaler Spannbaum
Der Algorithmus von Prim berechnet, wie der Kruskal-Algorithmus , den minimalen Spannbaum eines zusammenhängenden , gewichteten Graphen . Du weißt nicht was das ist? Kein Problem! Ein Spannbaum ist dann minimal, wenn er alle Knoten eines Graphen enthält. Zudem darf kein anderer Baum existiert, der die Knoten zu geringeren Kosten verbinden kann.
Ablauf des Prim Algorithmus
Aber wie berechnet man denn jetzt mit dem Prim-Algorithmus den minimalen Spannbaum?
Als erstes erstellen wir einen neuen Graphen . Dazu suchst du dir einen beliebigen Startknoten aus dem alten Graphen. Es ist egal welchen du zuerst auswählst. Am Ende wird sowieso jeder Knoten im minimalen Spannbaum enthalten sein.
Bis alle Knoten im neuen Graphen abgebildet sind wählst du immer genau die Kante mit den geringsten Kosten, die einen neuen Knoten mit dem Graphen verbindet. Dieses Schema wird wiederholt, bis der neue Graph alle Knoten des alten enthält.
Vielleicht ist dir bereits aufgefallen, dass der Algorithmus immer die aktuell beste Möglichkeit, nicht aber die global beste betrachtet. Aus diesem Grund fällt er in die Klasse der Greedy-Algorithmen . Was diese sind erklären wir dir in einem kurzen Video.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
Beispiel für Prims Algorithmus
Schauen wir uns nun den Prim-Algorithmus an einem Beispiel an.
Als Startknoten wählen wir einfach Knoten B. Jeder andere wäre aber ebenfalls völlig in Ordnung.
Werfen wir nun einen Blick auf alle Kanten, die im ursprünglichen Graphen von B ausgehen. Wir wählen die kürzeste, also die Kante von B zu E mit den Kosten von 13 und fügen sie zu unserem Graphen hinzu. Perfekt!
Diesen Schritt wiederholen wir. So kannst du erkennen, dass die kürzeste Kante, die einen neuen Knoten mit einem der Knoten unseres Teilgraphen verbindet, die Kante von E nach C ist. Auch diese fügen wir also hinzu.
Diese Schritte wiederholen wir so lange, bis wir alle Knoten in unserem neuen Graphen eingefügt haben.
Wie du siehst, haben wir nun alle Knoten miteinander verbunden. Einige Kanten des alten Graphen werden nicht genutzt. Diese sind überflüssig also lassen wir sie weg. Somit haben wir nun unseren minimalen Spannbaum gefunden.
Jetzt kannst du mithilfe des Prim-Algorithmus den minimalen Spannbaum eines beliebigen Graphen berechnen. Super simpel, oder?
Unterschied zwischen Prim und Kruskal Algorithmus
Der Unterschied zum Kruskal-Algorithmus liegt darin, wie der minimale Spannbaum aufgebaut wird. Beim Prim-Algorithmus wird mit einem Knoten gestartet. Von diesem ausgehend wird nach und nach ein Teilgraph gebildet. Der Kruskal-Algorithmus hingegen sortiert die Kanten nach den Gewichten und fügt sie in aufsteigender Reihenfolge hinzu.
Pseudocode Prim Algorithmus
Wie der Prim-Algorithmus implementiert werden kann, wird an diesem einfachen Pseudocode klar:
Initialisierung
Ausgangsgraph G
Erstelle neuen Graphen MST
Wähle Startknoten von G und füge ihn in MST hinzu
Iterationen
solange Knoten MST ≠ Knoten G
finde Kante mit min. Knotengewicht die mit Knoten aus MST verbunden ist und neuen Knoten zu MST hinzufügt
füge neue Kante zu MST hinzu
füge neuen Knoten zu MST hinzu
Output:
MST ist der Minimale Spannbaum von G
Prim Algorithmus — häufigste Fragen
(ausklappen)
Prim Algorithmus — häufigste Fragen
(ausklappen)-
Was ist ein Spannbaum?Ein Spannbaum ist ein Teilgraph, der alle Knoten eines zusammenhängenden Graphen verbindet, aber keine Kreise enthält. Dadurch gibt es zwischen zwei Knoten genau einen Weg. Ein Spannbaum hat bei
Knoten genau 
Kanten.
-
Wird der Spannbaum noch verwendet?Ein Spannbaum wird noch verwendet, weil er ein Netzwerk so verbindet, dass alle Knoten erreichbar sind, ohne dass unnötige Schleifen entstehen. Ein typisches Beispiel sind Computernetzwerke, in denen das Spanning Tree Protocol Schleifen verhindert. Auch viele Optimierungsaufgaben bauen auf Spannbäumen auf.
-
Welche Kante wählt man beim Prim-Algorithmus als Nächstes, wenn schon mehrere Knoten im Teilgraphen sind?Beim Prim-Algorithmus wählt man als nächste Kante die billigste Kante, die einen Knoten aus dem bisherigen Teilgraphen mit einem noch nicht enthaltenen Knoten verbindet. Dafür betrachtet man alle Kanten, die von irgendeinem Knoten im Teilgraphen nach außen führen, und nimmt die mit minimalen Kosten.
-
Was macht man, wenn beim Prim-Algorithmus mehrere mögliche Kanten die gleichen minimalen Kosten haben?Beim Prim-Algorithmus kann man bei gleichen minimalen Kosten eine der günstigsten Kanten auswählen, solange sie einen neuen Knoten an den Teilgraphen anschließt. Je nach Wahl kann am Ende ein anderer Spannbaum entstehen. Das bedeutet, dass der Graph mehrere minimale Spannbäume haben kann.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Graphenalgorithmen verstehen
Der Prim-Algorithmus ist ein bekanntes Verfahren aus den Graphenalgorithmen. Du modellierst Probleme als Graphen und arbeitest mit Knoten, Kanten und Gewichten, um Strukturen im Netzwerk zu finden. So erkennst du, wie Greedy-Entscheidungen Schritt für Schritt zu einer sinnvollen Gesamtlösung führen können. Weitere Videos dazu findest du in unserem Informatikbereich.