Motywacja

BFS używa kolejki (pierwsze weszło, pierwsze wyszło), dzięki czemu wierzchołki są przetwarzane dokładnie w kolejności ich odkrywania, co pozwala na eksplorację warstwa po warstwie.

Dlaczego warto poznać BFS?

• Najkrótsze ścieżki: w grafie nieważonym BFS znajduje ścieżkę o najmniejszej liczbie krawędzi od punktu początkowego do każdego innego wierzchołka.
• Prosty i liniowy: działa w czasie O(V + E), korzystając z kolejki i oznaczeń odwiedzonych wierzchołków.
• Wszechstronne zastosowanie: najkrótsze trasy w sieciach, drabinki słowne, rozwiązywanie labiryntów i przechodzenie drzewa poziomami — to wszystko zastosowania BFS.

Podobnie jak w DFS, dodajemy sąsiadów wierzchołka do kolejki w kolejności rosnącej, aby wyniki były przewidywalne.