Graf se kaze Graph :), cvorovi su verticles, a edge je veza izmedju cvorova, ne znam na srpskom izraz.

Sto se rastojanja izmedju 2 cvora tice, koliko se secam koristi se warshall-ov algoritam. Nije komplikovan. Imas u knjizi "Introduction to Algorithms" od Cormena, MIT Press izmedju ostalog i poglavlje (ili 2) posveceno grafovima. Ima je i na netu kao pdf, javi mi se na PM ako ne nadjes.

Evo jos 2:
1. Neka je dat skup S={1,2,...,n} n e N. Konstruisati graf G=(V,E) gdje je skup cvorova V=|S| a skup grana odredjen sa A~B ako i samo ako je A presjek B prazan skup.

2. Dat je aciklican digraf G sa n cvorova. Oznaciti cvorove grafa G brojevima 1,2,3...n
tako da ako je cvor x oznacen sa k tada su svi cvorovi do kojih se moze doci iz x oznaceni sa brojem vecim od k.

“Određivanje najkraćih rastojanja u netežinskom grafu
Najkraće rastojanje između dva čvora i i j u netežinskom grafu se definiše kao minimalan broj grana na putu između njih. Za nalaženje ovog rastojanja se može iskoristiti modifikovani algoritam obilaska grafa po širini. Čvor i se uzima kao početni čvor pri obilasku. U tom slučaju najkraće rastojanje nekog čvora od njega je jednako njegovom nivou. Zato u algoritam treba još uvesti jedan vektor nevoa čvora u, posle postavljanja odgovarajućeg bita visit u unutrašnjoj for petlji procedure BFS, treba još inkremetirati nivo čvora v preko kojeg se došlo do čvora u i taj rezultat zapamtiti kao nivo čvora u (l(u) = l[v] + 1). Ponovnim dolaskom do već posećenog čvora preko drugog prethodnika, ovo rastojanje se ne može smanjiti. Kada se poseti čvor j, traženo rastojanje je nađeno i algoritam može da završi rad. Pritom se najkraći put sastoji od grana BFS stabla i polazi od korena i do traženog čvora j. Ako se algoritam pusti da odradi do kraja, onda se u vektoru l dobijaju najkraća rastojanja od polaznog do svih drugih čvorova u grafu. “

Strukture podataka Milo V. Tomašević

Ovo je pseudo-kod BFS algoritma iz ove knjige.



Ovo sam sad našao pa idem da sad iskucam program pa ću ga ovdje okačit. Ostaje mi poslije još da nadjem ovo za neparnu konturu(ciklus).


http://www.elitesecurity.org/tema/50794
Ovo jeste slicno ali nije baš to što mi treba.

E da našao sam ovu knjigu ali je još nisam čitavu spustio. A ovaj Warshall-ov algoritam sam malo pogledao ali mi se čini da on služi za izračunavanje matrice puta. Mada nisam se mnogo udubljivao, kasnije ću.

Da, izracunava matricu puteva izmedju svih cvorova... samim tim i izmedju svaka 1 cvora :)
To mi je prvo palo na pamet.

Bila je vec za rastojanje izmedju dva chvora ...

2. Dat je aciklican digraf G sa n cvorova. Oznaciti cvorove grafa G brojevima 1,2,3...n
tako da ako je cvor x oznacen sa k tada su svi cvorovi do kojih se moze doci iz x oznaceni sa brojem vecim od k.

Preorder obilazak grafa u dubinu. Znachi pustish DFS, i za svaki chvor, kad ga posetish, pridruzish mu broj Counter, i Counter povecash za jedan ...

@RooTeR:
Ne bas. Odakle da znas od kog cvora da pocnes?

Ovaj algoritam zove se topolosko sortiranje. Ideja je sledeca:
Nadju se indegree-ovi svih cvorova (npr. DFS-om). Uzmemo one kojima je indegree 0, i stavimo ih na queue. Sa queue uvek uzimamo prvi cvor, numerisemo counterom (koji pocinje od 0, i povecava cim se nekom cvoru dodeli). Kad numerisemo neki cvor, izbacimo ivice koje iz njega polaze, i naravno updateujemo indegree za cvorove sa kojima su bili spojeni. Cim nekom cvoru indegree postane 0, dodajemo ga na queue. As simple as that.

Btw, Floyd-Warshall-ov algoritam sluzi za nalazenje najkracih puteva u bilo kom (dakle i tezinskom) grafu, i slozenosti je . Ako graf nije tezinski (dakle sve ivice imaju istu tezinu), najkraci putevi se mogu naci i BFS-om, pri cemu bi morao da se pusti BFS iz svakog cvora, pa bi konacna slozenost bila , sto je u opstem slucaju isto kao Floyd-Warshall. Moze se i pustiti i Dijkstra iz svakog cvora.

Ovaj algoritam(ne ovaj koji je iskucan nego ovaj koji je opisan) se zaustavlja cim se doce do trazenog cvora takoda ne trazi rastojanje do sledecih cvorova.

evo pogledajte ove slajdove sto sam prikacio uz poruku.

Nego, bio sam danas na konsultacije kod ove profesorice, i rekla mi je da postoji jedna teorema za ovo. Pa se rastojanje izmedju dva cvora racuna preko matrice susjedstva. Nasao sam to pa cu vam sjutra okaciti to i objasniti.

Ovo je teorema i posledica vezena za problem rastojanja između dva čvora. Pošto imam problem sa kucanjem u -u, pošto mi je ovo prvi put u životu da sam pokušao da ga koristim objasniću vam ovu teoremu. Kad budem savladao malo tex postaviću i punu teoremu.

Teorema: Neka je matrica susjedstva jednostavnog grafa G, tada element matrice , tada predstavlkja broj šetnji dužine l od cvora do cvora .

Posledica: Rastojanje izmedu 2 cvora je najkraca staza koja spaja ta dva cvora

Dakle radi se o tome da teorema kaže da kad stepenujemo matricu susjedstva prvo pojavljivanje nam daje rastojanje između čvora i čvora koje je jednako stepenu l. Ne znam da li ste me razumjeli.

A ovo je teorema vezana za ovaj drugi problem, da li dati graf sadrži neparni ciklus.

Teorema: Graf G je bipartitan akko ne sadrži neparne cikluse.

Sad idem ovo da isprogramiram. ;)




<sub>[Ovu poruku je menjao MrLimeni dana 15.05.2005. u 17:58 GMT+1]

[Ovu poruku je menjao MrLimeni dana 15.05.2005. u 18:01 GMT+1]</sub>

Koliko sam ja ukapirao, ti pricas o Floyd-Warshallovom algoritmu, a na ovom slajdu je prikazan BFS. Procitaj moj prethodni post i bice ti sve jasno:

Dakle, ono sto je prikazano na pps prezentaciji je BFS iz jednog cvora, sto ce naci najkraca rastojanja od njega do svih ostalih. Ako hoces i ostala rastojanja, markiras sve cvorove kao neprodjene, pa pustis BFS iz B, pa iz C, itd...



Da! Dokaz:

(=>) Trivijalno. Neka je graf G bipartitan sa biparticijom (A, B). Podjimo od nekog cvora a iz A. Svaki put neparne duzine dovodi nas do cvora u B, a svaki put parne do cvora u A. Kako treba da se vratimo u a da bi napravili ciklus, on mora biti parne duzine.

(<=) Nesto tezi smer. Nadjimo neko drvo razapinjanja u grafu G, i oznacimo ga sa T. Uzmemo neki, bilo koji cvor, v. Do svakog cvora mozemo iz v stici na jedinstven nacin iduci ivicama koje se nalaze u T. Sada tvrdimo da su one do kojih je put parne duzine u jednoj, a do kojih je neparne u drugoj particiji. Za svaku ivicu e (x, y) vazi jedno od sledeca 2:

(i) e se nalazi u T. U ovom slucaju je ili x pretposlednju cvor na v-y putu kroz T, ili je y pretposlednji cvor na v-x putu kroz T. U svakom slucaju duzine puteva do x i y su razlicite, pa su oni u razlicitim particijama.

(ii) e se ne nalazi u T. U ovom slucaju, x-y put u T, zajedno sa ivicom e pravi ciklus. Po (i) imamo da su cvorovi na x-y putu u T naizmenicno u jednoj i drugoj particiji. Posto je svaki ciklus paran, onda su x i y u razlicitim particijama.

QED

Inace, za proveru da li je graf bipartitan moze se koristiti obican DFS sa markiranjem cvorova crno-belo.

Ne znam jesmo li se mi razumjeli. Meni treba da ja unesem od kojeg do kojeg cvora mi treba rastojanje. Dakle od čvora x do čvora y. I onda BFS pustim od čvora x i kad čim naiđem na čvor y zaustavim algoritam. Ne treba mi da idem da nađem rastojanje između svih čvorova. Ali, mnogo bolje je ova metoda preko matrice susjedstva , to jest to meni treba. :)

OK, znaci treba ti samo rastojanje izmedju dva cvora. Pa dobro, radi kako hoces, ali stvarno ne mogu da verujem da moze bilo sta da ti bude lakse nego BFS (5-10 redova koda). A o slozenosti (vremenskoj) algoritma za mnozenje matrica da i ne govorim...

Ma znam ja to, nego ova profesorica je bas to trazila. pa cu odraditi na oba nacina :)))))

Evo ovo je kod koji sam iskucao za privi problem, rastojanje izmedju dva cvora. Ovo je verzija koja koristi ovu teoremu o matricama susjedstva. Odje je samo dio koda. a prikacio sam i kompletnu verziju sa datotekom "matrica.txt" koja cuva matricu susjedstva.


Nisam se nesto previse trudio oko menija i dodatnih opcija. Mislim da cu uradit ovaj program i u VB. A vi ako imate kakvih komentara, primjedbi ili pitanja samo navalite. ;)

HVALA SVIMA NA POMOCI.

Evo druga verzija onog prvog problema, rastojanje. Samo sad pomocu BFS pretrazivanja.



ovo je samo dio koda. Citav kod sam prikacio...