Prim’s Algorithmus ist ein effizienter Algorithmus zur Berechnung eines minimalen Spannbaums (MST) in einem gewichteten, zusammenhängenden Graphen. Der Algorithmus beginnt mit einem beliebigen Knoten und fügt schrittweise die Kante mit dem geringsten Gewicht hinzu, die einen Knoten im bereits gewählten Teilbaum mit einem Knoten außerhalb verbindet. Dieses Verfahren wird wiederholt, bis alle Knoten im Baum enthalten sind.
Der Algorithmus kann in folgenden Schritten zusammengefasst werden:
Die Laufzeit von Prim’s Algorithmus beträgt , wobei die Anzahl der Kanten und die Anzahl der Knoten im Graphen ist, insbesondere wenn ein Min-Heap oder eine Fibonacci-Haufen-Datenstruktur verwendet wird.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.