Algorithmus von Prim
Der Algorithmus von Prim ist ein Algorithmus zur Berechnung von minimal spannenden Bäumen in zusammenhängenden ungerichteten kantengewichteten Graphenen.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.
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.