Prims algoritme

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

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

  1. man har en graf med noder V og kanter E
  2. sett MST til å være en vilkårlig valgt node i V

Sålenge der er noder i V som ikke ligger i MST

  1. 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.
  2. legg ( u , v ) til MST

Avslutningsvis

  1. det minimale spenntre består av kantene i MST

Algoritmen har en tidskompleksitetO(|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|).

Eksempel[rediger | rediger kilde]

Image Beskrivelse Ukjent Nærmeste omkrets MST
Prim Algorithm 0.svg Den opprinnelige vektede graf. Hver kant har en angitt kostnad. Utgangspunkt er D. C, G A, B, E, F D
Prim Algorithm 1.svg Neste node som innlemmes i MST er A (til kostnad 5). Innlemmede kanter vises i grønt. C, G B, E, F A, D
Prim Algorithm 2.svg Dernest velges den rimeligste nabo til en av D eller A, hvilket blir F. C B, E, G A, D, F
Prim Algorithm 3.svg Etter at B (den rimeligste nabo til A, D og F) innlemmes i MST, ser en (merket med rødt) at noen av kantene ikke kan velges heretter, da de gir rundtur (syklus). null C, E, G A, D, F, B
Prim Algorithm 4.svg E innlemmes. null C, G A, D, F, B, E
Prim Algorithm 5.svg C innlemmes. null G A, D, F, B, E, C
Prim Algorithm 6.svg G er det eneste gjenstående, og innlemmes i det nå ferdige MST som har kostnad 39. null null A, D, F, B, E, C, G

Referanser[rediger | rediger kilde]

  1. ^ 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.
  2. ^ Robert Clay Prim, Shortest connection networks and some generalisations. Bell System Technical Journal, 36 (1957), side 1389–1401