Przeszukiwanie wszerz
Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).
Przebieg algorytmu
- Oznacz wszystkie wierzchołki grafu jako nieodwiedzone.
- Odwiedź wierzchołek źródłowy, dodaj go do kolejki Q.
- Dopóki kolejka Q nie jest pusta:
- Pobierz pierwszy wierzchołek z kolejki (usuwając go z niej).
- Odwiedź wszystkie jeszcze nieodwiedzone wierzchołki sąsiednie tego wierzchołka, dodaj je do kolejki Q.
Zwyczajowo przyjmuje się, że:
- nieodwiedzone wierzchołki są oznaczone jako białe,
- odwiedzone wierzchołki znajdujące się w kolejce Q oznaczone są jako szare,
- odwiedzone wierzchołki spoza kolejki Q (te, których sąsiedzi są na pewno odwiedzeni) oznaczone są jako czarne.
Złożoność
Oznaczmy przez v liczbę wierzchołków grafu i przez e liczbę jego krawędzi. Początkowa część algorytmu ma złożoność O(v) – oznaczamy każdy wierzchołek. Liczba relacji sąsiedztwa jest równa liczbie krawędzi (lub jej dwukrotności, jeśli graf jest nieskierowany), więc złożoność czasowa głównej pętli algorytmu to O(e). Łącznie złożoność algorytmu jest więc rzędu O(v+e).
Jeśli każdy wierzchołek jest osiągalny ze źródła (po zakończeniu działania algorytmu nie będzie nieodwiedzonych wierzchołków), to e ≥ (v−1). Przy takim założeniu złożoność czasowa algorytmu wynosi O(e).
Zastosowanie
Za pomocą przeszukiwania grafu wszerz można wyznaczyć najkrótsze pod względem liczby krawędzi (ale nie wag!) ścieżki między wierzchołkiem źródłowym a pozostałymi wierzchołkami. Algorytm ten może być więc wykorzystany do rozwiązania szczególnego przypadku problemu najkrótszej ścieżki, gdy wszystkie krawędzie mają taką samą dodatnią wagę. Przeszukiwanie wszerz jest częścią składową niektórych bardziej zaawansowanych algorytmów grafowych, np. algorytmu Edmondsa-Karpa.
Bibliografia
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Liczba głosów: 3.
- Przeszukiwanie w głąb
- Przeszukiwanie wszerz
Dodano: 21 listopada 2017 17:35, ostatnia edycja: 30 stycznia 2019 15:55.
Zobacz też
Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).
Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.
Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).
Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.