Parcurgerea grafurilor în adâncime

Foarte mulţi algoritmi de prelucrare a grafurilor necesită examinarea tuturor nodurilor unui graf.Pentru aceasta este necesară definirea unei strategii de traversare a grafului.Se poate vorbi în principal de două tehnici de traversare: - în adâncime (Depth First) - în lăţime (Breadth First) În explicarea modului de funcţionare a primei variante se foloseşte un şir de întregi, VIZITAT, de lungime n cu ajutorul căruia se marchează nodurile deja “vizitate” pentru a evita trecerea de mai multe ori prin acelaşi nod.Cu alte cuvinte VIZITAT[j] = 1 dacă nodul j a fost deja atins şi VIZITAT[j] = 0 în caz contrar.Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate. Procedura recursivă care asigură parcurgerea unui graf în adâncime începând cu un anumit vârf i: Procedura Parcurgere_în_adâncime(i) pentru toate vârfurile k adiacente cu vârful i execută daca vârful k este neparcurs atunci se parcurge vârful k apel parcurgere_în_adâncime(k) Ieşirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii incepând cu un anumit vârf i să rămână în graf vârfuri neparcurse.În această situaţie apelul procedurii se repetă pentru un alt vârf iniţial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în apel.Condiţiile interne care apar în problemele particulare de backtracking pot impune o parcurgere integrală sau numai parţială a grafului.Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf în adâncime: Descarca toata lectia