Traversarea grafurilor în lăţime sau Breadth-First este numită astfel pentru că
lărgeşte, uniform, frontiera dintre nodurile descoperite şi cele nedescoperite, pe lăţimea
frontierei. Aceasta înseamnă că algoritmul descoperă toate vârfurile aflate la
distanţa k faţă de ns înainte de a descoperi vreun vârf la distanţa k+1. Cu alte cuvinte
traversarea în lăţime a grafurilor presupune faptul că după vizitarea unui anumit nod v,
sunt parcurşi toţi vecinii nevizitaţi ai acestuia, apoi toţi vecinii nevizitaţi ai acestora din
urmă până la vizitarea tuturor nodurilor grafului(spunem că două noduri sunt vecine dacă
sunt adiacente).Implementarea acestei metode se face folosind o structură de date de tip coadă. Cozile sunt structuri de date în care elementele sunt inserate la un capăt (sfârşitul cozii) şi sunt suprimate de la celălalt capăt (începutul cozii). Ele implementează politica "primul venit - primul servit". Asupra unei cozi acţionează operatori specifici cum ar fi: iniţializare coadă, test de coadă vidă, adăugă un element la sfârşitul cozii, scoate un element de la începutul cozii. Cozile pot fi implementate static(cu variabile de tip tablou unidimensional) sau dinamic.
În acest caz coada este iniţializată cu un nod oarecare al grafului. La fiecare pas, pentru nodul aflat în vârful cozii, se adaugă la coadă toţi vecinii nevizitaţi ai nodului respectiv după care se şterge din coadă primul nod.Fie graful din figura următoare care are n = 8 noduri.
Niciun comentariu:
Trimiteți un comentariu