Primov algoritem je algoritem, ki v grafu oziroma v matriki povezav poišče povezavo, ki je najcenejša, a je različna od 0. To povezavo oz. točki (vozlišči), ki pripadata tej povezavi, in povezava sama sestavljajo drevo. Nato pa za vse ostale točke, ki še niso vključene v drevo, izračunamo, katera točka v drevesu je najbližje ali j ali k, ter jo vključimo v drevo. Ko točko vključimo v drevo, ji postavimo neskončno vrednost cene. Za preostale točke, ki še niso v drevesu, znova pogledamo, ali je na novo dodana točka bližje k točki, ki še ni vključena v drevo kot točka, ki je bila pred dodajanjem nove točke tej točki najbližje.
Algoritem je leta 1930 razvil češki matematik Vojtěch Jarník. Leta 1957 ga je neodvisno od njega razvil ameriški matematik in računalnikar Robert Clay Prim, nizozemski računalnikar Edsger Wybe Dijkstra pa ga je leta 1959 na novo odkril. Zaradi tega algoritem včasih imenujejo algoritem DJP, Jarníkov algoritem ali Prim-Jarníkov algoritem.
Časovna zahtevnost Primovega algoritma je Θ(n2)
Postopek procedure Prim (n, c, vrednost, drevo) // n - točke, c - povezave begin vrednost := c[k,l] // povezava z min ceno (drevo[1,1], drevo[1,2]) := (k,2) // 1.veja min vpetega drevesa for i:= 1 to n do begin if c[i,l] < c[i,k] then r[i] := l else r[i] := k r[k], r[l] := 0 for i:= 2 to n-1 do begin // poišči 1<= j <= n tako, da r[j] != 0 in c[j, r[i]] = min (drevo[i,1], drevo[i,2]) := (i, r[i]) vrednost := vrednost + c[i,r[i]] r[i] := 0 for k := 1 to n do begin if r[k] != 0 and c[k,r[k]] > c[k,i] then r[k] := i end end end end
Zunanje povezave - v angleščini: Kruskalov in Primov algoritem Demonstracija primovega algoritma Animacijski prikaz delovanja Primovega algoritma
Kategorija:Algoritmi Kategorija:Vpeta drevesa Kategorija:1930 v znanosti