Algorithmus von Prim

Algorithmus:
Der Algorithmus von Prim berechnet zu einem gewichteten Graphen $G=(V,E)$ einen minimalen Spannbaum, indem er von den bereits besuchten Knoten die minimale Kante (Prioritätswarteschlange) zu einem unbesuchten Knoten zum Spannbaum hinzunimmt.

Komplexität:
Der Algorithmus von Prim benötigt Zeit $O(n+m)$, wenn alle Operationen der Prioritätswarteschlange in $O(1)$ ausführbar sind, genauer gesagt $n$ Aufrufe von ExtractMin und $m$ Aufrufe von Insert. Bei Fibonacci Heaps ergibt sich somit $O(n \log n + m)$. Die Verwendung von Buckets ist aufgrund der zusätzlichen Bedingungen i.A. nicht möglich. Dennoch ist der Algorithmus von Prim für dichte Graphen eines der schnellsten Verfahren.