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.
