Outline · Standard · [ Linear+ ]

> Pomoc Oko Grafova

darkokg
post Mar 6 2009, 05:20 PM
Post #1





Group: Članovi
Joined: 1-April 08
Member No.: 992
Status: Van MGa
Ime i prezime: Darko Antonijevic



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
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
 
Reply to this topicStart new topicStart Poll
Replies(1 - 14)
maxydelanoche
post Mar 6 2009, 06:50 PM
Post #2





Group: Članovi
Joined: 3-May 06
From: Zion
Member No.: 61
Status: Van MGa



Sigurna sam da ce ti primena nekog od ovih: http://en.wikipedia.org/wiki/List_of_algor...raph_algorithms algoritama pomoci biggrin.gif


--------------------
Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena.

I'm doing the best I ever did, I'm doing the best that I can.

www.viva-fizika.org
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
pyost
post Mar 6 2009, 06:55 PM
Post #3


Deus Ex Makina
Group Icon

Group: Administratori
Joined: 25-January 06
From: Beograd
Member No.: 2
Status: Bivši učenik MGa
Škola/Razred: RAF



Mozda da brojis na koliko nacina su koja dva cvora povezana? Ako izmedju neka dva cvora postoji samo 1 put, onda je to trazeni put... Valjda unsure.gif


--------------------
Baby, it's a violent world.

Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10]
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
calamity
post Mar 6 2009, 07:03 PM
Post #4





Group: Članovi
Joined: 4-April 07
From: Cambridge, MA, USA
Member No.: 491
Status: Van MGa
Škola/Razred: MIT junior, RAF alumna, Grobarska alumna



Cek, treba da nadjes bilo koji put koji povezuje sve cvorove ako postoji?

Kako mi se cini, mozes da pustis neki algoritam za obilazak grafova (guglaj Depth First Search ili Breadth First Search). Krenes iz jednog cvora, pa obilazis dok mozes. Ako si obisao sve cvorove, postoji takav put (negde usput ga zapamti ako ti treba).

Mada hmmm... ne znam koliko je zgodno tako pamtiti put... i sta u stvari radis u zadatku ako recimo imas 4 cvora a povezani su ti (1, 2), (1,3), (1,4). Ako treba da pamtis i vracanje u prvi cvor i sta ja znam, mooooozda je to prilcno zeznuto tongue.gif smile.gif A mozda i ja ne kapiram zadatak.

This post has been edited by calamity: Mar 6 2009, 07:06 PM
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maxydelanoche
post Mar 6 2009, 07:10 PM
Post #5





Group: Članovi
Joined: 3-May 06
From: Zion
Member No.: 61
Status: Van MGa



Eeeee, da... ovaj, dakle biggrin.gif

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


--------------------
Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena.

I'm doing the best I ever did, I'm doing the best that I can.

www.viva-fizika.org
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
pyost
post Mar 6 2009, 07:30 PM
Post #6


Deus Ex Makina
Group Icon

Group: Administratori
Joined: 25-January 06
From: Beograd
Member No.: 2
Status: Bivši učenik MGa
Škola/Razred: RAF



Errr... Mislim da ovo poslednje bas i nije od pomoci XD.gif


--------------------
Baby, it's a violent world.

Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10]
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
darkokg
post Mar 6 2009, 07:34 PM
Post #7





Group: Članovi
Joined: 1-April 08
Member No.: 992
Status: Van MGa
Ime i prezime: Darko Antonijevic



Hvala na odgovorima, ali jos kad bih i nesto ukapirao. Prvo, ne znam sta znaci DFS, ako bi mi malo pojasnili, mozda bih i mogao da uradim nesto...
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
pyost
post Mar 6 2009, 07:35 PM
Post #8


Deus Ex Makina
Group Icon

Group: Administratori
Joined: 25-January 06
From: Beograd
Member No.: 2
Status: Bivši učenik MGa
Škola/Razred: RAF



Depth First Search (google)


--------------------
Baby, it's a violent world.

Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10]
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
darkokg
post Mar 6 2009, 07:36 PM
Post #9





Group: Članovi
Joined: 1-April 08
Member No.: 992
Status: Van MGa
Ime i prezime: Darko Antonijevic



QUOTE(pyost @ Mar 6 2009, 07:55 PM)
Mozda da brojis na koliko nacina su koja dva cvora povezana? Ako izmedju neka dva cvora postoji samo 1 put, onda je to trazeni put... Valjda unsure.gif
*


Mislim da ovo nije resenje. Moze da postoji vise parova koji su povezani samo jednim putem a da u isto vreme povezuju iste delove grafa....
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maxydelanoche
post Mar 6 2009, 07:39 PM
Post #10





Group: Članovi
Joined: 3-May 06
From: Zion
Member No.: 61
Status: Van MGa



Ovo moje je resenje sto posto. Treba ti modifikovani DFS koji sam opisala. Izgooglaj sta je DFS, iskodiraj ga i shvati lepo, a onda pokusaj da implementiras i ovo sto sam ti rekla.


--------------------
Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena.

I'm doing the best I ever did, I'm doing the best that I can.

www.viva-fizika.org
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
darkokg
post Mar 6 2009, 07:40 PM
Post #11





Group: Članovi
Joined: 1-April 08
Member No.: 992
Status: Van MGa
Ime i prezime: Darko Antonijevic



Da, sad sam na prvo citanje shvatio da moze da mi posluzi, HVALA!!!!
Nadam se da cu se izvuci......
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maxydelanoche
post Mar 6 2009, 07:45 PM
Post #12





Group: Članovi
Joined: 3-May 06
From: Zion
Member No.: 61
Status: Van MGa



Imam kod za DFS gotov, ali radi sa listama povezanosti, a ne sa matricama, tako da sumnjam da bi ti bio od koristi XD.gif Al' ima sigurno dosta o tome na netu, tako da ces se sigurno snaci ako se pomucis dovoljno wink.gif


--------------------
Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena.

I'm doing the best I ever did, I'm doing the best that I can.

www.viva-fizika.org
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
calamity
post Mar 6 2009, 09:33 PM
Post #13





Group: Članovi
Joined: 4-April 07
From: Cambridge, MA, USA
Member No.: 491
Status: Van MGa
Škola/Razred: MIT junior, RAF alumna, Grobarska alumna



@maxydelalonche
Ja apsolutno nisam razumela tvoje resenje a znam i sta je DFS i most itd biggrin.gif Ne mogu da ispratim smile.gif

edit: jos jednom procitah... i opet ne kapiram sta pokusavas da kazes biggrin.gif

This post has been edited by calamity: Mar 6 2009, 09:34 PM
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
maxydelanoche
post Mar 6 2009, 09:37 PM
Post #14





Group: Članovi
Joined: 3-May 06
From: Zion
Member No.: 61
Status: Van MGa



Aaaaa, moras malo da sednes i da dobro razmislis kako da implementiras to, ali u sustini ne mora nista vise da se objasni XD.gif a i mrrrzi me soproud.gif ja sam bila uspela da na osnovu samo takvog objasnjenja napravim program, uspece i darkokg smile.gif


--------------------
Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena.

I'm doing the best I ever did, I'm doing the best that I can.

www.viva-fizika.org
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
calamity
post Mar 6 2009, 09:43 PM
Post #15





Group: Članovi
Joined: 4-April 07
From: Cambridge, MA, USA
Member No.: 491
Status: Van MGa
Škola/Razred: MIT junior, RAF alumna, Grobarska alumna



M' ja ne razumem ni sta radis uopste ;D No, nebitno, ako darkokg razume, sve super smile.gif
User is offlineProfile CardPM
Go to the top of the page
+Quote Post

Reply to this topicTopic OptionsStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members: