Bei der Beschreibung des Algorithmus von Prim heisst es:
Beginne mit einem Baum, der allein aus einer Ecke besteht. Ordne alle Kanten von dieser Ecke aus nach ihren Kosten in einer Prioritätswarteschlange. Füge nun jeweils immer aus dieser jeweils die nächste Kante mit den geringsten Kosten ein, die keinen Zyklus erzeugt. Dann füge alle von der freien Ecke ausgehenden zulässigen Kanten in die Prioritätswarteschlange ein.
Der Sinn der Anwendung einer Prioritätswarteschlange ist, dass immer die aktuell lokal günstigste Kante verwendet wird, um den lokal am günstigsten erscheinenden Weg weiter zu verfolgen. Ein Beispiel für das Arbeiten mit einer Prioritätswarteschlange als Liste:
Schritt | Zustand | erste heraus | hinein (z. B.) |
---|---|---|---|
1 | ( 12 , 31 , 45 , 77 ) | 12 | 19 , 51 |
2 | ( 19 , 31 , 45 , 51 , 77 ) | 19 | 2 , 91 |
3 | ( 2 , 31 , 45 , 51 , 77 , 91 ) | ... | ... |