Redigerer 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]],<ref>[[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.</ref> og senere, uavhengig, av [[Robert Clay Prim]] i [[1957]]<ref>[[Robert Clay Prim]], Shortest connection networks and some generalisations. ''Bell System Technical Journal'', 36 (1957), side 1389–1401</ref> (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==
{| border=1 cellspacing=0 cellpadding=5
! Image !! Beskrivelse !! Ukjent !! Nærmeste omkrets !! MST
|-
|[[Fil:Prim_Algorithm_0.svg|200px]]
|Den opprinnelige vektede graf.  Hver kant har en angitt kostnad.  Utgangspunkt er ''D''.

| C, G
| A, B, E, F
| D
|-
|[[Fil:Prim Algorithm 1.svg|200px]]
|Neste node som innlemmes i MST er ''A'' (til kostnad 5).  Innlemmede kanter vises i grønt.
| C, G
| B, E, F
| A, D
|-
|[[Fil:Prim Algorithm 2.svg|200px]]
|Dernest velges den rimeligste nabo til en av ''D'' eller ''A'', hvilket blir ''F''.
| C
| B, E, G
| A, D, F
|-
|[[Fil:Prim Algorithm 3.svg|200px]]
|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
|-
|[[Fil:Prim Algorithm 4.svg|200px]]
|''E'' innlemmes.
| null
| C, G
| A, D, F, B, E
|-
|[[Fil:Prim Algorithm 5.svg|200px]]
|''C'' innlemmes.
| null
| G
| A, D, F, B, E, C
|-
|[[Fil:Prim Algorithm 6.svg|200px]]
|''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
|}

== Bevis for korrekthet ==
{{kildeløst avsnitt}}
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 Y<sub>1</sub> være et kjent minimalt spenntre for grafen P. Hvis Y<sub>1</sub> = 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 Y<sub>1</sub>, 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 Y<sub>1</sub> 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 Y<sub>2</sub> være treet vi får ved å fjerne kanten ''f og legge til e.'' Det er lett å se at Y<sub>2</sub> er sammenhengende, har samme antall noder som Y<sub>1</sub> en total vekt som ikke er større enn Y<sub>1</sub>. 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==
<references/>
{{Autoritetsdata}}

[[Kategori:Grafalgoritmer]]
[[Kategori:Vitenskap i 1930]]
[[Kategori:Vitenskap i 1957]]