5.2 Algorithmus von Prim

Ein noch schnellerer Algorithmus zur Berechnung des MST ist der Algorithmus von Prim. Er ist ein gutes Beispiel für einen Greedy-Algorithmus:

Starte mit einem Knoten.

Wähle die billigste Kante, die den bisher aufgebauten Baum mit dem Rest verbindet.

genauer:

     Initialisiere einen Baum mit dem Knoten A
     Initialisiere Heap mit den Nachbarn von A
     REPEAT
          entferne den billigsten Knoten x aus dem Heap
          füge x dem Baum hinzu
          update den Heap
     UNTIL heap_is_empty

Der verwendete Heap muß dabei leistungsfähiger als ein normaler Heap sein (siehe später). In unserem vorangegangenen Beispiel ergibt sich dann folgender Ablauf:

Für einen Nachbarn y von x ist also folgendes zu tun:

$\bullet$ falls y im Baum: tue nichts

$\bullet$ falls y im Heap: falls p(y) > c(x,y) setze p(y) : = c(x,y) dann führe Heapupdate durch (hier tauchen Probleme auf, die ein normaler Heap nicht bewältigen kann)

$\bullet$ falls y im Rest: füge y in den Heap ein mit p(y) : = c(x,y)

Der Aufwand des Prim-Algorithmus liegt in O(|E| · log |V|) , da jede Kante mit Aufwand O(log |V|) zweimal bearbeitet wird.

Bei dichtbesetzten Graphen (|E| $\simeq$ |V|²,|V| = n) ergibt sich für die Aufwände von Kruskal und Prim:

$\bullet$ Kruskal: n ² · logn ² = n ² · logn · 2

$\bullet$ Prim: n ² · log n