Prims algoritme
Fra Wikipedia, den frie encyklopedi
Prims algoritme er en grådig algoritme innen grafteori som finner minste spenntre i en vektet graf. Den ble oppdaget av Vojtěch Jarník i 1930,[1] og senere, uavhengig, av Robert Clay Prim i 1957[2] (samt Edsger Dijkstra, 1959). Således benevnes den også DJP-algoritmen eller Jarniks algoritme.
Initielt
- man har en graf med noder V og kanter E
- sett MST til å være en vilkårlig valgt node i V
Sålenge der er noder i V som ikke ligger i MST
- finn en kant i E som til lavest kostnad (og uten at det gir syklus), kobler en node u i MST, med en node v som ikke er i MST.
- legg ( u , v ) til MST
Avslutningsvis
- det minimale spenntre består av kantene i MST
Algoritmen har en tidskompleksitet på O(|E| log|V|), og er avhengig av hvordan man finner rimeligste tilleggs-kant i hver runde. Med en Fibonnaciheap, vil tidskompleksiteten bli O(|E| + |V|log|V|).
[rediger] Eksempel
[rediger] Referanser
- ^ Vojtěch Jarník, O jistém problému minimálním, Práce Moravské Přírodovědecké Společnosti, 6, 1930, sider 57-63.
- ^ Robert Clay Prim, Shortest connection networks and some generalisations. Bell System Technical Journal, 36 (1957), side 1389–1401