Algorithmus von Prim
Der Algorithmus von Prim ist ein Algorithmus zur Berechnung von minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphen.
Der Algorithmus arbeitet folgendermaßen:
- Wähle einen beliebigen Knoten als Startgraph T.
- Solange T noch nicht alle Knoten enthält,
- suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und
- füge diese Kante und den damit verbundenen Knoten zu T hinzu.
Zur effizienten Implementierung wird zu jedem Knoten die kürzeste Kante, die ihn mit T verbindet (falls vorhanden) und ihr Gewicht in einer geeigneten Priority Queue (z.B. in einem Fibonacci-Heap) gespeichert. Dies ermöglicht schnell eine Kante minimalen Gewichts zu finden, die einen Knoten, der nicht in T ist, mit T verbindet. Mit Fibonacci-Heaps ergibt sich eine optimale Laufzeit von .
Fibonacci-Heaps oder andere geeignete Priority Queues sind nicht ganz einfach zu implementieren. Daher verwendet man statt des Algorithmus von Prim oft auch den Algorithmus von Kruskal, der das Problem aber nicht ganz so effizent löst, insbesondere bei dichten Graphen, d.h. Graphen viele Kanten besitzen. Der Kruskal-Algorithmus arbeitet schneller, wenn die Kanten nach Gewichtungen vorsortiert sind.