Parcurgerea în lățime

Se parcurge vârful de start, apoi vecinii acestuia, apoi vecinii nevizitați ai acestora, etc, până când sunt vizitate toate vârfurile accesibile. Practic, pentru a stabili ordinea de vizitare se folosește o coadă, iar pentru a stabili dacă un vârf a fost sau nu vizitat se foloseşte un vector caracteristic.

Algoritmul este:

adaugăm în coadă vârful inițial și îl vizităm
cât timp coada este nevidă
- extragem un element din coadă
- determinăm vecinii nevizitați ai vârfului extras, îi vizităm și îi adăugăm în coadă
- eliminăm elementul din coadă

Observație

Dacă graful nu este conex, în urma parcurgerii nu se vor vizita toate vârfurile.

Exemplu

Vârfurile grafului au fost parcurse în ordinea: 5 2 4 7 1 3 6 8 9.

În urma parcurgerii în adâncime, muchiile folosite pentru parcurgere formează un arbore. Acest arbore este graf parțial al grafului dat (dacă graful este conex), și se numește arbore parțial de parcurgere. Pentru graful de mai sus, arborele de parcurgere pornind din vârful 5 este:

Acest arbore poate fi considerat arbore cu rădăcină, aceasta fiind chiar vârful de start, 5,

În acest caz, odată cu parcurgerea se poate construi și vectorul de "tați" t[] al arborelui. În acest exemplu el este:

k 1 2 3 4 5 6 7 8 9
t[k] 2 5 2 5 0 4 5 7 7

Din vectorul de tați al unui arbore se poate determina ușor pentru un vârf oarecare un lanț de la acel vârf la rădăcina arborelui. Arborii obținuți în urma parcurgerii în lățime au proprietatea că lanțul de la vârful de pornire la oricare vârf accesibil din graf obținut din arborele de parcurgere are lungime minimă.

Implementare C++

Funcţia de mai jos presupune că un graf cu n vârfuri este memorat prin intermediul matricei de adiacenţă, vectorul x[] reprezintă coada, vectorul v[], aceste variabile fiind declarate global. Funcţia returnează numărul de elemente care au fost vizitate.

int bfs(int start)

{

int i,k,st,dr;

//initializez coada

st=dr=1;

x[1]=start;

v[start]=1;//vizitez varful initial

while(st<=dr)//cat timp coada nu este vida

{

k=x[st];//preiau un element din coada

for(i=1;i<=n;i++)//parcurg varfurile

if(v[i]==0 && a[k][i]==1)//daca i este vecin cu k si nu este vizitat

{

v[i]=1;//il vizitez

x[++dr]=i;//il adaug in coada

}

st++;//sterg din coada

}

return dr;//returnam numarul de varfuri vizitate

}

Vezi și: