[ Outline ] · Standard · Linear+ Pomoc Oko Grafova

[darkokg]

Potrebno je da ukoliko imam matricu povezanosti cvorova (0 ako nisu povezani i 1 ako jesu) pronadjem put koji ukoliko ne bi postojao, graf ne bi bio jedna celina vec bi se podelio na dva dela tako da je iz jednog nemoguce stici u drugi deo.

Ne morate kucati ceo kod, pretostavljam da je poprilicno dug, dajte mi samo ideju ili bar linkove ka nekoj literaturi koja se bavi ovom problematikom posto ja nisam mogao da pronadjem nista.

Pomogli bi mi ukoliko mi neko odgovori do 20-21h veceras, posle... i nije toliko bitno jer mi zadatak treba za sutra.....

EDIT:
Da, znam da sam pogresio u naslovu, ali izgleda da ne moze da se izmeni sada..... lol

This post has been edited by darkokg: Mar 6 2009, 05:23 PM

[maxydelanoche]

Eeeee, da... ovaj, dakle

grana bez koje graf ne bi bio povezan zove se most... Jel' znas sta je DFS? Kada ides DFS-om po grafu, ukoliko pritom neki cvor u ima neko dete cvor v u DFS stablu, pri cemu vazi el[v]<ulazni[u], onda je grana koja spaja ta dva cvora - most. Pri tome je ulazni niz dobijen uobicajeno DFS pretragom, a u nizu el je na mestu i minimalni od ulaznih stepenova cvorova do kojih se moze stici unazad granama grafa od cvora i, tj najdalji predak cvora i povezan sa delom DFS stabla koji sadrzi potomke cvora i. Ako i nema nijednog takvog pretka, onda je el[i]=ulazni[i].

This post has been edited by maxydelanoche: Mar 6 2009, 07:16 PM