BFS (Breadth-First Search) to algorytm przeszukiwania grafu lub drzewa wszerz, czyli poziomami. Najpierw odwiedzane są wierzchołki położone najbliżej punktu startowego, potem kolejne, coraz dalsze.
Jaka struktura danych jest używana w BFS?
W algorytmie BFS stosuje się kolejkę FIFO. Oznacza to, że pierwszy dodany element zostanie jako pierwszy zdjęty z kolejki.
Dzięki temu algorytm zachowuje kolejność odwiedzania wierzchołków poziomami:
- dodaje wierzchołek startowy do kolejki,
- pobiera pierwszy element z kolejki,
- odwiedza jego nieodwiedzonych sąsiadów,
- dodaje tych sąsiadów na koniec kolejki,
- powtarza proces, aż kolejka będzie pusta.
Przykładowy pseudokod
BFS(start):
utwórz pustą kolejkę
oznacz start jako odwiedzony
dodaj start do kolejki
dopóki kolejka nie jest pusta:
v = pobierz z początku kolejki
dla każdego sąsiada v:
jeśli nie był odwiedzony:
oznacz jako odwiedzony
dodaj do kolejki
Zastosowania BFS
BFS wykorzystuje się m.in. do:
- znajdowania najkrótszej ścieżki w grafie nieważonym,
- sprawdzania spójności grafu,
- przeszukiwania drzewa poziomami,
- rozwiązywania problemów typu labirynt lub sieć połączeń.
Najważniejsze do zapamiętania
W BFS kluczowa jest kolejka, ponieważ zapewnia kolejność FIFO. Stos nie jest poprawną odpowiedzią, ponieważ stos prowadziłby do przeszukiwania w głąb, czyli DFS.