Parcurgerea grafurilor orientate

             Prin algoritmul BF se realizeaza o parcurgere a grafului „în lăţime“. Se vizitează un vârf iniţial s, apoi vecinii săi (vârfurile adiacente cu s), după aceea vecinii vecinilor lui s (nevizitaţi încă), etc.

Observatie!

• Dacă graful nu este conex nu se pot vizita toate vârfurile.

Structuri de date necesare pentru implementare sunt:

1. Matrice de adiacenţă (sau alte variante de reprezentare): a

2. Coada (în care se memorează în ordinea parcursă nodurile vizitate): c
– p, u - indicatorii primului şi ultimului element din coadă

3. Vectorul nodurilor vizitate: viz
– viz[i]=1, dacă i a fost vizitat
– viz[i]=0, altfel

              Parcurgerea BF(Breath First) se efectuează prin utilizarea structurii numită coadă, având grijă ca un nod să fie vizitat o singură dată.

              Atunci când un nod a fost introdus în coadă, se marchează ca vizitat.
Observatie!

•   Algoritmul se adaptează astfel încât să poată fi luaţi în considerare toţi vecinii unui nod.

Exemplu: 
X = {1, 2, 3, 4, 5}; 

U = {(1,2), (2,1), (1,3), (2,5), (4,1)}; 

         Algoritmul DF (Depth First) se caracterizează prin faptul că realizează o parcurgere a grafului „în adâncime“ atât cât este posibil.

• Parcurgerea începe cu un vârf s ales inițial.

• Prelucrarea unui vârf conduce la prelucrarea primului său vecin încă nevizitat, apoi se prelucrează primul vecin al acestuia care nu a fost încă vizitat, etc.

Structuri de date necesare implementării:

1. Matrice de adiacenţă (sau alte variante): a

2. Stiva: s (în care se memorează nodurile în ordinea parcurgerii). Dacă se implementează varianta recursivă, se va folosi stiva procesorului

3. Vectorul nodurilor vizitate: viz

Exemplu: