Przeszukiwanie wszerz

Przeszukiwanie wszerz (1) Przeszukiwanie wszerz, przykład

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

  1. Oznacz wszystkie wierzchołki grafu jako nieodwiedzone.
  2. Odwiedź wierzchołek źródłowy, dodaj go do kolejki Q.
  3. Dopóki kolejka Q nie jest pusta:
    1. Pobierz pierwszy wierzchołek z kolejki (usuwając go z niej).
    2. 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.
Ocena: +3 Tak Nie
Liczba głosów: 3.

Dodano: 21 listopada 2017 17:35, ostatnia edycja: 30 stycznia 2019 15:55.

REKLAMA

Zobacz też

Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

→ Czytaj całość

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość
Polityka prywatnościKontakt