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: n6e20eo
- 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 VIZITATaji = 1 daca nodul j a fost deja atins si VIZITATaji = 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) Aparcurge graful in adancimeS
VIZITATasi:=1; pentru fiecare nod w adiacent cu s executa daca VIZITATawi = 0 atunci apel adancime(w) sfarsit daca; sfarsit pentru; sfarsit procedura;

pentru toate nodurile w executa
VIZITATawi:=0; sfarsit pentru; apel adancime(1);
Conex:=true; pentru toate nodurile w executa daca VIZITATawi = 0 atunci conex:=false; sfarsit daca; sfarsit pentru;
Sfarsit functie;