Primov algoritam
Primov algoritam je algoritam u teoriji grafova koja nalazi minimalno razapinjuće stablo za povezani težinski graf. To znači da nalazi podskup grana koje formiraju stablo koje uključuje sve čvorove, takav da je ukupna težina stabla minimizovana. Algoritam je 1930. godine izumeo Vojtjeh Jarnik, a kasnije nezavisno od njega informatičar Robert Prim 1957, i ponovo Edsher Dajkstra 1959. godine. Stoga se nekad naziva DJP algoritmom ili Jarnikovim algoritmom.
Opis
[uredi | uredi izvor]Algoritam postepeno povećava veličinu stabla počevši od jednog čvora, dok ne poveže sve čvorove.
- Ulaz: Povezan težinski graf G(V, E)
- Inicijalizacija: V' = {x}, gde je x proizvoljan čvor iz V, E'= {}
- ponavljanje dok ne postane V'=V:
- Izaberi granu (u, v) iz E sa minimalnom težinom, takvu da je u iz V' a v nije iz V' (ako ima više grana iste težine, izabrati proizvoljnu)
- Dodaj v u V', i (u, v) u E'
- Izlaz: G(V', E') je minimalno razapinjuće stablo
Vremenska kompleksnost
[uredi | uredi izvor]| Struktura podataka grana minimalne težine | Vremenska kompleksnost (ukupno) |
|---|---|
| matrica susedstva, pretraga | V² |
| binarni hip (kao u pseudokodu prikazanom ispod) i lista povezanosti | O((V + E) log(V)) = E log(V) |
| Fibonačijev hip i lista povezanosti | E + V log(V) |
Jednostavna implementacija predstavljanjem grafa matricom susedstva i pretraživanjem niza težina kako bi se pronašla grana najmanje težine zahteva vreme O(V²). Korišćenje jednostavnog binarnog hipa i liste povezanosti, može se pokazati da je Primovom algoritmu potrebno vreme od O(Elog V) gde je E broj grana, a V je broj čvorova. Korišćenjem sofisticiranijeg Fibonačijevog hipa, ovo se može spustiti na O(E + Vlog V), što je znatno brže kada je graf dovoljno gust da je E (Vlog V).
Primer
[uredi | uredi izvor]| Slika | Opis | Nesusedni čvorovi | Susedni čvorovi | Skup rešenja |
|---|---|---|---|---|
|
Ovo je početni težinski graf. On nije stablo, jer po definiciji stablo nema ciklova, a ovaj dijagram sadrži ciklove. Brojevi pored grana označavaju njihove težine. Nijedna grana nije obeležena, a čvor D je proizvoljno izabran za početnu tačku. | C, G | A, B, E, F | D |
|
Drugi izabrani čvor je čvor najbliži čvoru D: udaljenost A je 5, udaljenost B je 9, udaljenost E je 15, a udaljenost F je 6. Od ovih brojeva, 5 je najmanji, tako da obeležavamo čvor A i granu DA. | C, G | B, E, F | A, D |
|
Zatim biramo čvor koji je najbliži bilo čvoru D bilo čvoru A. udaljenost B od D je 9, i 7 od A, udaljenost E je 15, a F je 6. 6 je najmanji broj, pa biramo čvor F i granu DF. | C | B, E, G | A, D, F |
|
Algoritam nastava na isti način. Obeležavamo čvor B, čija udaljenost od A je 7. | null | C, E, G | A, D, F, B |
|
U ovom slučaju možemo da biramo između C, E, i G. Udaljenost C od B je 8, E od B je 7, a G od F je 11. E je najbliže, pa biramo čvor E i granu EB. | null | C, G | A, D, F, B, E |
|
Sada su dostupni samo čvorovi C i G. Udaljenost C od E je 5, a udaljenost G od E je 9. Biramo C, kao i granu EC. | null | G | A, D, F, B, E, C |
|
Čvor G je jedini preostali čvor. Njegova udaljenost od F je 11, a od E je 9. E je bliže, pa obeležavamo granu EG. Sada su obeleženi svi čvorovi, i minimalno razapinjuće stablo je označeno zelenom. U ovom slučaju, minimalna težina je 39. | null | null | A, D, F, B, E, C, G |
Dokaz korektnosti
[uredi | uredi izvor]Neka je P povezan, težinski graf. U svakoj iteraciji Primovog algoritma, mora se naći grana koja spaja čvor u podgrafu sa čvorom van podgrafa. Kako je P povezan, uvek će postojati putanja do svakog čvora. Izlaz Primovog algoritma, Y je stablo, jer su grana i čvor dodati Y povezani. Neka je Y1 minimalno razapinjuće stablo od P. Ako je Y1=Y onda je Y minimalno razapinjuće stablo. U suprotnom, neka je e prva grana dodata tokom konstrukcije Y koja nije u Y1, a V je skup čvorova povezanih granama dodatim pre e. Tada je jedna strana grane e u V a druga nije. Kako je Y1 razapinjuće stablo od P, postoji putanja u Y1 koja spaja dve krajnje tačke. Dok se prolazi ova putanja, mora se proći grana f koja spaja čvor u V sa nekim koji nije u V. Sada, u iteraciji kada se e dodaje Y, f smo takođe mogli da dodamo, i dodali bismo je umesto e da je njena težina bila manja od e. Kako f nije dodata, zaključujemo da
- w(f) ≥ w(e). (w(f) je težina od f)
Neka je Y2 graf dobijen uklanjanjem f i dodavanjem e u Y1. Lako je pokazati da je Y2 povezan, ima isti broj grana kao Y1, i njegova ukupna težina nije veća od Y1, stoga je takođe minimalno razapinjuće stablo od P i sadrži e i sve grane dodate pre njega tokom konsrukcije V. Ponavljanjem ovih koraka će se konačno dobiti minimalno razapinjuće stablo od P koje je identično Y. Ovo pokazuje da je Y minimalno razapinjuće stablo.
Neki od drugih algoritama koji rešavaju ovaj problem su Kruskalov algoritam i Boruvkin algoritam.
Literatura
[uredi | uredi izvor]- V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (in Czech)
- R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
- D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3.. Section 23.2: The algorithms of Kruskal and Prim, pp.567-574.
