Parcurgerea grafurilor in adancime

DOWNLOAD REFERAT

Preview referat: Parcurgerea grafurilor in adancime

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
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. « mai multe referate din Diverse