Primov algoritem

Iz MaFiRaWiki

V podčlanku /NeznanAvtor najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.


Primov algoritem se uporablja za iskanje najcenejšega vpetega drevesa v omrežju (minimalno vpeto drevo). Drevo začnemo graditi iz poljubnega vozlišča, ki je že samo zase vpeto drevo in nato dodajamo najkrajšo povezavo, dokler ne dobimo celega vpetega devesa.

Časovna zahtevnost Primovega algoritma je O(n2)

Vsebina

Algoritem

  • Začnemo s poljubnim vozliščem, ki je že samo zase vpeto drevo (v našem primeru npr. vozlišče a)
  • Dokler ne dodamo n-1 vozlišč, ponavljamo:
    • izberemo najcenejšo povezavo med vozlišči v doslej zgrajenemu drevesu in vozlišči, ki še niso del drevesa in z njo ne naredimo cikla. (To je osnovni korak). Če sta dve povezavi z enakimi cenami, izberemo tisto, katera ne naredi cikla. Če nobena povezava ne naredi cikla, izberemo eno izmed niju.
    • to povezavo dodamo in ponavljamo, dokler nam ostane še kaj prostih vozlišč.

Primer

Slika: Primov.jpg

Glej tudi

- Kruskalov algoritem

Zunanje povezave

- v angleščini:

Osebna orodja