Make your own free website on Tripod.com

prema Primovom i Kruskalovom algoritmu

Metoda najkraceg stabla

Primov algoritam je vrlo jednostavan za pracenje. Pocetna tacka se bira proizvoljno i ona odmah postaje dio grafa. Svaka sljedeca tacka se dodaje ako se ustanovi da je udaljenost između bilo koje tacke iz grafa i bilo koje slobodne tacke najmanja upravo za tu tacku i neku tacku koja je već u grafu.Postupak se iterativno nastavlja sve dok sve ne ostane ni jedna slobodna tacka , odnosno dok sve tacke ne budu ukljucene u graf. Jezikom pseudocoda :
1. Izaberi proizvoljan pocetni cvor,
2. Nadji njemu najblizi cvor i taj cvor postaje dio grafa,
3. Nadji grafu najblizi slobodni cvor,
4. Iterativno ponavljaj postupak pod tackom 3. dok svi cvorovi ne budu ukljuceni u graf.
Kruskalov algoritam za pronalazenje najkraceg stabla grafa je tkzv. sebicni (greedy) algoritam zbog toga sto on obradjuje uvijek najmanju dostupnu ivicu (granu) grafa. Grane kandidati za ulazak u graf jesu sve moguce kombinacije pocetnih tacaka s tim što se izbjegava dupliranje grana npr. grana a- b je jednaka grani b-a pa granu b-a ne treba ukljucivati u moguce kombinacije . Grafu se prikljucuje najmanja dostupna grana pazeci da se pri tome ne zatvori ciklus.Jezikom pseudocoda,
1. Sortirati sve grane-kandidate za ulazak u graf,
2. Prikljuci najmanju granu grafu ako se tim prikljucivanjem ne zatvara ciklus,
3. Iterativno ponavljaj postupak pod tackom 2. dok sve pocetne tacke ne postanu dio grafa.

MNS - BOSANSKI.EXE (489 KB)

SEMINARSKI RAD

ON-LINE PREZENTACIJA RADA