Zanimalo bi me kako radi primov algoritam ili ako je kruskalov bolji....moze pseudokod ili jednostavno rjecima, hvala...
Primov algoritam
oba su dobra, i relativno su kratki, ako želiš naučiti prima preporučio bih ti da prvo naučiš dijsktrin algoritam za najkraći put, jer primov radi na tom principu, a kruskalov radi ovako:
u jedan niz spremi sve edgeve i sortiraj ih po tezini, od najmanje do najvece, na pocetku je svaki cvor sam u "svom stablu", zatim ides kroz edgeve kako su sortirani i za svaki edge spojis stabla u kojima se nalaze cvorovi koje taj edge povezuje, i to je zapravo sve, sad jos ostaje pitanje kako ćeš efikasno raditi spajanja cvorova, za to se koristi Disjoint-Set struktura koju mi se sad ne da bas objasnjavati, ali za pocetak mozes napravit taj spajanja u obicnim nizovima ili vektorima, a poslije naucis o disjoint setu, ima na topcoderu jedan dobar tutorijal, a vjerujem da ima i na wikipediji
u jedan niz spremi sve edgeve i sortiraj ih po tezini, od najmanje do najvece, na pocetku je svaki cvor sam u "svom stablu", zatim ides kroz edgeve kako su sortirani i za svaki edge spojis stabla u kojima se nalaze cvorovi koje taj edge povezuje, i to je zapravo sve, sad jos ostaje pitanje kako ćeš efikasno raditi spajanja cvorova, za to se koristi Disjoint-Set struktura koju mi se sad ne da bas objasnjavati, ali za pocetak mozes napravit taj spajanja u obicnim nizovima ili vektorima, a poslije naucis o disjoint setu, ima na topcoderu jedan dobar tutorijal, a vjerujem da ima i na wikipediji
Molio bih gospodu moderatore ili admina da mi posalju test primjer 6 na moj mail (mislav.balunovic@gmail.com) ili da ga ovdje napisu... hvala
Ne treba vise
@gates:
Pa Dijkstra uzima najjeftiniji put do sada i ne zanima je za najjeftiniju granu; dok Prim radi obrnuto - uzima najjeftiniju granu koja ne pravi konturu i briga ga za najjeftiniji put, cak se nigde i ne racuna. Zar ne?
Sem sto su oba algoritma greedy, ja ne vidim sta im je slicno.
@mbalunovic: Moderatori jos ne mogu da vide test primere. Nisam bas upucen o kom zadatku je rec, ali mozda zadatak postoji na http://www.yuoi.nis.edu.yu/takmicenja.html, pa probaj i tamo potraziti, ili se moze izgoogleati. Hajde ako ti nije problem daj zadatak ;)
Pa Dijkstra uzima najjeftiniji put do sada i ne zanima je za najjeftiniju granu; dok Prim radi obrnuto - uzima najjeftiniju granu koja ne pravi konturu i briga ga za najjeftiniji put, cak se nigde i ne racuna. Zar ne?
Sem sto su oba algoritma greedy, ja ne vidim sta im je slicno.
@mbalunovic: Moderatori jos ne mogu da vide test primere. Nisam bas upucen o kom zadatku je rec, ali mozda zadatak postoji na http://www.yuoi.nis.edu.yu/takmicenja.html, pa probaj i tamo potraziti, ili se moze izgoogleati. Hajde ako ti nije problem daj zadatak ;)
Ah, sad sam vidio da cak nsiam ni spomenuo o cem je rijec, inace zadatak kablovi sa dna liste zadataka... inace, rjesio sam ga tako da mi vise ne trebaju primjeri
da, u redu je to sto govoris, samo ih mozes jako slicno implementirati( dijsktru i prima ), moja recimo implementacija izgleda gotovo jednako...