|
Titlul: Circuit in graf orientat Scris de: Stefan Istrate din Februarie 19, 2006, 08:56:35 De ceva timp ma tot gandesc la o chestie si nu ma prind... Cum reusesc sa determin un circuit intr-un graf orientat? M-ar interesa o solutie cu DF sau BF, utilizata cu liste de adiacenta (asta ar fi optim).
Titlul: Circuit in graf orientat Scris de: Vlad Berteanu din Februarie 19, 2006, 09:32:55 Vezi ca a fost la campion o problema in care trebuia sa scoti ciclurile distincte dintr-un graf...se numea police ( anu asta la grupa large printre primele runde ).
Oricum ideea e ca faci un DF si in momentul in care gasesti un nod marcat inseamna ca poti inchide un ciclu. Titlul: Circuit in graf orientat Scris de: VladS din Februarie 19, 2006, 11:09:43 Fii mai explicit. Sunt mai multe tipuri de circuite in graf.
Titlul: Circuit in graf orientat Scris de: Stefan Istrate din Februarie 19, 2006, 19:34:31 Citat din mesajul lui: vladcyb1 Vezi ca a fost la campion o problema in care trebuia sa scoti ciclurile distincte dintr-un graf...se numea police ( anu asta la grupa large printre primele runde ). Oricum ideea e ca faci un DF si in momentul in care gasesti un nod marcat inseamna ca poti inchide un ciclu. Problema Police de la campion e in grafuri neorientate si se rezolva cu determinarea tuturor ciclurilor disjuncte. Pe mine ma intereseaza determinarea tuturor circuitelor disjuncte intr-un graf orientat. Si nu stiu daca mai merge la fel de bine parcurgerea DF. Titlul: Circuit in graf orientat Scris de: Filip Cristian Buruiana din Februarie 19, 2006, 20:47:13 Citat Cum reusesc sa determin un circuit intr-un graf orientat? Daca am inteles bine ce vrei, faci DFS si cand gasesti o muchie de intoarcere ( legatura de la nodul curent sa fie un nod inca neterminat ) atunci ai un ciclu. Titlul: Circuit in graf orientat Scris de: Stefan Istrate din Februarie 20, 2006, 08:37:52 (http://i48.photobucket.com/albums/f210/stef2n/graf.jpg)
Pentru graful orientat din figura parcurgerea DF ar fi : 1 2 3 4 5 6 7 Problema apare cand ajung la muchia 5 - 2 . 2 a fost vizitat inaintea lui 5, deci s-ar parea ca muchia 5 - 2 inchide un circuit. Totusi lucrurile nu stau asa. Cum poate fi evitata o astfel de situatie? Titlul: Circuit in graf orientat Scris de: andreit1 din Februarie 20, 2006, 19:07:01 Cred ca poti rezolva asta cu inca un vector care tine minte pentru fiecare nod daca este sau nu in stiva. Un nod se introduce in stiva la prima intalnire a lui si se elimina dupa ce au fost analizati toti vecinii sai( asta daca faci recursiv, pentru ca altfel e evident).
Trebuie sa mai fi atent la faptul ca din nodul 1 este posibil sa nu poti vizita toate celelalte noduri si atunci va trebui sa pornesti din fiecare nod inca nevizitat. Complexitatea ramane O(n+m) pentru ca treci o singura data prin fiecare muchie si nod. Titlul: Circuit in graf orientat Scris de: Silviu-Ionut Ganceanu din Februarie 21, 2006, 12:46:42 Nice picture stef2n =D>
Silviu Titlul: Circuit in graf orientat Scris de: Stefan Istrate din Februarie 21, 2006, 16:23:38 andreit1: Mersi mult! Ideea ta mi-a fost de mare ajutor! =D>
silviug: Ma bucur ca poza mea nu a trecut neobservata. E creatie proprie. De fapt, improvizatie de moment. :D |