Prims algoritme

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,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. og senere, uavhengig, av Robert Clay Prim i 1957Robert Clay Prim, Shortest connection networks and some generalisations. Bell System Technical Journal, 36 (1957), side 1389–1401 (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 det 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|).

Eksempel
 Image  Beskrivelse  Ukjent  Nærmeste omkrets  MST200pxDen opprinnelige vektede graf.  Hver kant har en angitt kostnad.  Utgangspunkt er D. C, G A, B, E, F D200pxNeste node som innlemmes i MST er A (til kostnad 5).  Innlemmede kanter vises i grønt. C, G B, E, F A, D200pxDernest velges den rimeligste nabo til en av D eller A, hvilket blir F. C B, E, G A, D, F200pxEtter 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, B200pxE innlemmes. null C, G A, D, F, B, E200pxC innlemmes. null G A, D, F, B, E, C200pxG 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

 Bevis for korrekthet 

La P være en sammenhengende graf. For hver iterasjon må Prims algoritme finne en kant som kobler sammen en node i en subgraf av P med en node utenfor subgrafen. Siden P er sammenhengende vil det alltid være en vei til alle nodene. La resultatet av Prims algoritme være Y. Vi vet at Y er et tre siden kanten og noden som ble lagt til Y er sammenhengende. La Y1 være et kjent minimalt spenntre for grafen P. Hvis Y1 = Y så er Y et minimalt spenntre for P. Hvis ikke så la e være den første kanten som ble lagt til ved å sette sammen Y og som ikke er med i Y1, og V være mengden som inneholder nodene koblet sammen av de kantene som ble lagt til før e. Da vil den ene enden av e være i mengden V og den andre ikke. Siden Y1 er et spenntre for P er det slik at en vei T må koble disse sammen. Hvis man følger veien T må man finne en kant f som kobler en node i V til en node som ikke er i V. Så da e ble lagt til treet Y ville f ha blitt lagt til i stedet for e hvis vekten var mindre enn e og siden f ikke ble lagt til må vi konkludere med at vekten til f er større eller lik vekten til e. La Y2 være treet vi får ved å fjerne kanten f og legge til e. Det er lett å se at Y2 er sammenhengende, har samme antall noder som Y1 en total vekt som ikke er større enn Y1. Det er derfor også et minimalt spenntre for grafen P som inneholder e og kantene som var lagt til før e. Hvis vi repeterer trinnene ovenfor kan vi finne et minimalt spenntre for P som er lik Y.

Referanser

Kategori:Grafalgoritmer
Kategori:Vitenskap i 1930
Kategori:Vitenskap i 1957