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: 0 Tak Nie
Liczba głosów: 0.

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

REKLAMA

Zobacz też

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

→ Czytaj całość

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość
Polityka prywatnościKontakt