Primov algoritem

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 Θ(n²)

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: