Circuit in graf orientat

[•stef2n]

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).

[•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.

[VladS]

Fii mai explicit. Sunt mai multe tipuri de circuite in graf.

[•stef2n]

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.

[•filipb]

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.

[•stef2n]

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?

[andreit1]

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.

[•silviug]

Nice picture stef2n  

Silviu

[•stef2n]

andreit1: Mersi mult! Ideea ta mi-a fost de mare ajutor!  
silviug: Ma bucur ca poza mea nu a trecut neobservata. E creatie proprie. De fapt, improvizatie de moment.