Parcurgere în lățime (BFS)

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

BFS (Breadth First Search) este una dintre cele două parcurgeri des folosită î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, folosesc principiul parcurgerii BFS (exemplu: Lee).