Primov algoritem

Iz Wikipedije, proste enciklopedije

Primov algoritem je algoritem, ki v grafu oz. v matriki povezav poišče povezavo, ki je najcenejša, a je različna od 0. To povezavo oz. vozlišči, ki pripadata tej povezavi in povezava sama sestavljajo drevo. Nato pa za vsa ostala vozlišča, ki še niso vključena v drevo, izračunamo, katero vozlišče v drevesu je najbližje ali j ali k ter ga vključimo v drevo. Ko vozlišče vključimo v drevo, mu postavimo neskončno vrednost cene. Za preostala vozlišča, ki še niso v drevesu znova pogledamo, ali je na novo dodano vozlišče bližje h vozlišču, ki še ni vključeno v drevo kot vozlišče, ki je bilo pred dodajanjem novega vozlišča temu vozlišču najbližje.

Časovna zahtevnost Primovega algoritma je Θ(n2)

[uredi] Postopek

procedure Prim (n, c, vrednost, drevo)
// n - vozl., 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

[uredi] Zunanje povezave

- v angleščini: