De ce contează?
Arunci o pietricică într-un lac liniștit. Din punctul de impact pleacă o undă care se propagă în cercuri concentrice: întâi atinge apa imediat din jur, apoi inelul următor, apoi cel de după. Niciun punct mai îndepărtat nu e atins înainte de unul mai apropiat. BFS explorează un graf exact așa — în valuri, de la sursă spre exterior, un nivel de distanță la fiecare pas.
Intuiția
Vrei să afli, plecând dintr-un nod, în câți pași (muchii) ajungi la fiecare alt nod. Ideea de bază: explorezi nodurile în ordinea distanței. Mai întâi sursa (distanță 0), apoi toți vecinii ei direcți (distanță 1), apoi vecinii vecinilor încă nedescoperiți (distanță 2), și tot așa. Pentru că nu sari niciodată un inel mai apropiat, prima dată când atingi un nod ai garantat drumul cel mai scurt până la el.
Cine impune ordinea asta? Coada FIFO. Nodurile de la distanța k intră în
coadă înaintea celor de la distanța k+1, deci ies tot înaintea lor — tot
nivelul k e procesat complet înainte de orice nod de nivel k+1. Asta e
proprietatea-cheie a BFS: în grafuri neponderate, primul drum găsit este
drumul minim în muchii.