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.

Animație configurabilă pentru parcurgerea BFS!

În urma parcurgerii în lățime, 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, iar vectorul v[] este vectorul caracteristic prin care stabilim dacă un vârf al grafului a fost sau nu vizitat – 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
}