Der Algorithmus von Prim ist ein Algorithmus zur Berechnung eines minimal spannenden Bäumes in einem zusammenhängenden ungerichteten kantengewichteten Graphen.

Arbeitsweise

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.

Effiziente Implementierung

Zur effizienten Implementierung wird zu jedem Knoten die kürzeste Kante, die ihn mit T verbindet (falls vorhanden) und ihr Gewicht in einem geeigneten Heap (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 O(m + nlogn).

Vergleich mit Kruskal-Algorithmus

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. bei Graphen, die viele Kanten besitzen. Der Kruskal-Algorithmus arbeitet schneller, wenn die Kanten nach Gewichtungen vorsortiert sind.

Literatur

• Minimum Spanning Tree und 2-Approximation der TSP-Tour (http://web.informatik.uni-bonn.de/I/Lehre/Seminare/ProSem0001/Themen/Ausarbeitung/TSP.pdf), Michael Daumen, 2000

Siehe auch

• Algorithmus von Dijkstra