Note de curs, probleme algoritmică, 18 noiembrie 2013

În acest curs am discutat despre problema 1077 - Travelling Tours.

Cerința

Pentru un graf dat, se cere să se identifice un număr maximal de cicluri independente. Un ciclu este independent de celelalte dacă conține cel puțin o muchie care nu se regăsește în niciunul din celelalte cicluri.

Soluția

Pornind de la o parcurgere (în adâncime sau în lățime) a nodurilor se observă că fiecare muchie de întoarcere (care leagă nodul curent de un nod deja parcurs) formează (închide) un ciclu. În plus, se observă că muchia de întoarcere care l-a format apare doar în acel ciclu.

Folosind această modalitate de construire a ciclurilor independente obținem M - (N - 1) cicluri independente, câte unul pentru fiecare muchie de întoarcere, care este și numărul maxim de astfel de cicluri.

Mod de implementare

Implementarea este diferită, în funcție de tipul de parcurgere pe care o folosim.

Parcurgerea în adâncime

Implementarea bazată pe o parcurgere în adâncime este cea mai simplă, dar are dezavandajul că, în general, produce cicluri foarte lungi.

În timpul parcurgerii trebuie să memorăm într-o stivă sau într-un vector nodurile pe care le-am parcurs pentru a ajunge de la rădăcină la nodul curent. De asemenea, trebuie să calculăm adâncimea fiecărui nod parcurs. De fiecare dată când revizităm un nod avem garanția că nodul respectiv face parte din drumul de la rădăcină la nodul curent. Cunoscându-i adâncimea și folosind drumul de la rădăcină vom putea determina ușor nodurile (și muchiile) care formează ciclul.

Parcurgerea în lățime

Implementarea bazată pe o parcurgere în lățime este mai complicată, dar are avandajul că, în general, produce cicluri foarte scurte.

În timpul parcurgerii trebuie să memorăm arborele de vizitare sub forma unui vector de tați (trebuie să memorăm din ce nod am vizitat prima dată fiecare nod). De asemenea, trebuie să calculăm adâncimea fiecărui nod parcurs. De fiecare dată când revizităm un nod avem garanția că nodul respectiv se află la aceeași adâncime sau o adâncime cu 1 mai mică decât nodul curent.

Cunoscând adâncimea nodului curent și a nodului revizitat și mergând din părinte în părinte, putem identifica primul stămoș comun al celor două noduri. Reconstituind și unind drumurile de la strămoșul comun la cele două noduri obținem nodurile (și muchiile) ciclului.