Wprowadzenie

Witamy ponownie w serii Algorytmy grafowe! Po przeszukiwaniu w głąb przechodzimy do przeszukiwania wszerz (BFS) — drugiego podstawowego sposobu przechodzenia grafu.

Podczas gdy DFS zagłębia się w graf, BFS eksploruje go warstwami: najpierw wierzchołek początkowy, potem wszystkich jego sąsiadów, następnie wszystkie wierzchołki oddalone o dwa kroki i tak dalej. To właśnie kolejność warstwami sprawia, że BFS znajduje najkrótsze ścieżki w grafach nieważonych.

Tak jak w pozostałej części serii, graf jest podany jako n (liczba wierzchołków, od 0 do n - 1) oraz edges — płaska tablica nieskierowanych par [u0, v0, u1, v1, ...].

Zaczynajmy!