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:
