Primov algoritem/NeznanAvtor

Iz MaFiRaWiki

Algoritem je postopek, skupek navodil, za izvedbo določenega opravila ali naloge. Računalniški algoritem je sestavljen iz korakov. Vsak korak izvede svoje opravilo in je logično povezan z drugimi koraki. Število korakov algoritma je končno. Vrstni red korakov je točno določen in je odvisan od naloge.

Vsebina

Algoritem

Osnovna ideja Primovega algoritma je začeti z poddrevesom, ki vsebuje eno samo vozlišče in iterativno dodajati najkrajšo povezavo, dokler ne dobimo celega vpetega devesa. Preprosta implementacija te ideje zahteva, da se v eni iteraciji za vsako vozlišče v trenutnem drevesu pregledajo vse povezave. V drevo se doda najkrajša povezava z nekim vozliščem, ki še ni v drevesu. To ponavljamo dokler niso vsa vozlišča v našem poddrevesu.

Postopek

Podan je povezan graf G=(V,E) in cena povezave w (funkcija, ki slika iz množice E v množico pozitivnih realnih števil R+).
Poiščimo minimalno vpeto drevo:

  1. Naj bo števec i=0 in si izberimo začetno vozlišče u0. Množica vozlišč vpetega drevesa je zdaj S0={u0} in pot P(u0)=0, P(v)= neskončna, kjer v<>u0. Če graf G vsebuje samo eno vozlišče smo končali, drugače nadaljujemo z 2. korakom.
  2. Za vsak v iz S\V zamenjaj sedanjo pot P(v) z minimalno potjo min{P(v), w(v,ui)}.
  3. Poišči vozlišče v, ki je minimalno (ima najmanjšo pot iz ui) in naj bo to vozlišče ui + 1.
  4. Naj bo Si+1=Si unija {ui+1}.
  5. Povečaj števec i=i+1. Če je i enak številu vozlišč v grafu G manj 1 (i=|V|-1), končaj, drugače se vrni na 2. korak.

Časovna zahtevnost

Časovna zahtevnost Primovega algoritma je O(n2)

Primer


Slikovni prikaz

Slikovni prikaz, kako s pomočjo Primovega algoritma na povezanem grafu poiščemo minimalno vpeto drevo.


Prvotno drevo:

Koraki Primovega algoritma:
1. Korak:


2. Korak:


3. Korak:


4. Korak:


5. Korak:


6. in zadnji korak:


Koda

Koda Primovega algoritme v Javi.

  1. public class Prim {
  2. public static int [] prim (WeightedGraph G, int s) {
  3. final int [] razdalja = new int [G.size()];
  4. final int [] opazovanje = new int [G.size()]; // opzovanje vozlisc v drevesu
  5. final boolean [] obiski = new boolean [G.size()]; // vsi napacni zacetki
  6. for (int i=0; i<razdalja.length; i++) {
  7. razdalja[i] = Integer.MAX_VALUE;
  8. }
  9. razdalja[s] = 0;
  10. for (int i=0; i<razdalja.length; i++) {
  11. final int next = minVertex (razdalja, obiski);
  12. obiski[next] = true;
  13. final int [] n = G.neighbors(next);
  14. for (int j=0; j<n.length; j++) {
  15. final int v = n[j];
  16. final int d = G.getWeight(next,v);
  17. if (razdalja[v] > d) {
  18. razdalja[v] = d;
  19. opazovanje[v] = next;
  20. }
  21. }
  22. }
  23. return opazovanje;
  24. }
  25. private static int minVertex (int [] razdalja, boolean [] v) {
  26. int x = Integer.MAX_VALUE;
  27. int y = -1; // graf ni povezan
  28. for (int i=0; i<razdalja.length; i++) {
  29. if (!v[i] && razdalja[i]<x) {y=i; x=razdalja[i];}
  30. }
  31. return y;
  32. }
  33. } // class Prim

Glej tudi

Osebna orodja