Parcurgerea grafurilor in adancime
Foarte multi algoritmi de prelucrare a grafurilor necesita examinarea tuturor nodurilor unui graf.Pentru aceasta este necesara definirea unei strategii de traversare a grafului.Se poate vorbi in principal de doua tehnici de traversare:
- in adancime (Depth First)
- in latime (Breadth First)
In explicarea modului de functionare a primei variante se foloseste un sir de intregi, VIZITAT, de lungime n cu ajutorul caruia se marcheaza nodurile deja "vizitate" pentru a evita trecerea de mai multe ori prin acelasi nod.Cu alte cuvinte VIZITAT[j] = 1 daca nodul j a fost deja atins si VIZITAT[j] = 0 in caz contrar.Vom spune despre un nod i ca a fost explorat daca are toate nodurile adiacente vizitate.
Procedura recursiva care asigura parcurgerea unui graf in adancime incepand cu un anumit varf i:
Procedura Parcurgere_in_adancime(i)
pentru toate varfurile k adiacente cu varful i executa
daca varful k este neparcurs
atunci se parcurge varful k
apel parcurgere_in_adancime(k)
Iesirea din recursivitate se produce in momentul in care nu se mai gasesc varfuri neparcurse adiacente cu varfurile parcurse deja. Este posibil ca dupa un apel al procedurii incepand cu un anumit varf i sa ramana in graf varfuri neparcurse.In aceasta situatie apelul procedurii se repeta pentru un alt varf initial (dintre varfurile neparcurse) pana la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie sa asigure parcurgerea varfului utilizat in apel.Conditiile interne care apar in problemele particulare de backtracking pot impune o parcurgere integrala sau numai partiala a grafului. Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf in adancime:
Procedura Backtracking(i)
pentru toate varfurile k adiacente cu varful i executa
daca varful k este neparcurs si sunt indeplinite conditiile de continuare
atunci se parcurge varful k
se utilizeaza varful k in solutie
daca s-a ajuns la o solutie se afiseaza
apel Backtracking(k)
Folosind aceasta tehnica de traversare ne propunem sa raspundem la intrebarea:
Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?
Conform acestei metode explorarea unui nod este suspendata ori de cate ori un nou varf este vizitat.Pentru graful G daca pornim din varful 1, vizitarea nodurilor se va face in ordinea: 1,2,4,8,5,6,3,7.
Urmatoarea functie returneaza true daca graful este conex si false in caz contrar folosind tehnica parcurgerii in adancime:
Function Conex: boolean;
Procedura adancime(s) {parcurge graful in adancime}
VIZITAT[s]:=1;
pentru fiecare nod w adiacent cu s executa
daca VIZITAT[w] = 0 atunci apel adancime(w)
sfarsit daca;
sfarsit pentru;
sfarsit procedura;
pentru toate nodurile w executa
VIZITAT[w]:=0;
sfarsit pentru;
apel adancime(1);
Conex:=true;
pentru toate nodurile w executa
daca VIZITAT[w] = 0 atunci
conex:=false;
sfarsit daca;
sfarsit pentru;
Sfarsit functie;
