Parcurgere în lățime (BFS)

Parcurgerea nodurilor unui graf este o modalitate de a accesa toate cele în care putem ajunge din unul dat, avansând pe muchii.

BFS (Breadth First Search) este una dintre cele două parcurgeri des folosite în algoritmică.

Aplicațiile de bază sunt: determinarea componentei conexe a nodului de pornire și determinarea drumurilor de cost minim de la nodul de pornire la toate celelalte. Problema de minim are sens dacă graful nu are costuri pe muchii (sau, echivalent, toate muchiile au același cost).

Algoritmii de la capitolul cozi, studiați mai devreme în cadrul nivelului 2, folosesc principiul parcurgerii BFS (exemplu: Lee).