- Bieżący
- W kolejce
- Odwiedzone
- Ścieżka
Przeszukiwanie wszerz (BFS)
Przeszukiwanie wszerz bada graf pierścieniami: najpierw każdy wierzchołek obok startu, potem każdy w odległości dwóch krawędzi i tak dalej. Robi to za pomocą kolejki: pierwszy wchodzi, pierwszy wychodzi. Kliknij wierzchołek, aby od niego zacząć, wybierz cel, jeśli chcesz, i przechodź przez przeszukiwanie krok po kroku. Zobaczysz, jak kolejka rośnie i maleje, jak każdy wierzchołek dostaje odległość i jak pojawia się najkrótsza ścieżka. Naciśnij Odtwórz, aby obejrzeć przeszukiwanie, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby szukać najkrótszej ścieżki do niego. Liczba na każdym wierzchołku to jego odległość od startu, a rząd pod grafem to kolejka. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Kliknij wierzchołek, aby uczynić go startem. Aby szukać ścieżki, przełącz kliknięcie na Cel i kliknij inny wierzchołek.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce przeszukiwania.
- Obserwuj kolejkę pod grafem i odległość na każdym wierzchołku. Nowy graf tworzy inny graf do wypróbowania.
Jak działa przeszukiwanie wszerz
Wstaw wierzchołek startowy do kolejki z odległością 0. Potem powtarzaj: weź wierzchołek z początku kolejki i sprawdź każdego z jego sąsiadów. Sąsiad, którego jeszcze nie widziano, dostaje odległość o jeden większą niż wzięty wierzchołek, zapamiętuje ten wierzchołek jako drogę, którą do niego dotarto, i trafia na koniec kolejki. Sąsiadów widzianych wcześniej się pomija. Gdy kolejka jest pusta, każdy osiągalny wierzchołek ma swoją odległość.
Dlaczego znajduje najkrótsze ścieżki
Kolejka wydaje wierzchołki w kolejności, w jakiej je znaleziono, a wierzchołki są znajdowane pierścień po pierścieniu: wszystkie w odległości 1 trafiają do kolejki przed jakimkolwiek w odległości 2 i tak dalej. Gdy więc wierzchołek zostaje osiągnięty po raz pierwszy, dzieje się to ścieżką o najmniejszej możliwej liczbie krawędzi. Cofając się po zapamiętanych wierzchołkach od celu do startu, dostaje się tę ścieżkę. Liczą się tu tylko krawędzie; gdy krawędzie mają różne długości, potrzebny jest algorytm Dijkstry.
Często zadawane pytania
Czym jest przeszukiwanie wszerz?
To sposób badania grafu od wierzchołka startowego: najpierw odwiedza się wszystkich jego sąsiadów, potem ich sąsiadów i tak dalej, pierścień po pierścieniu. Kolejka przechowuje wierzchołki w kolejności, w jakiej je znaleziono.
Czy przeszukiwanie wszerz znajduje najkrótszą ścieżkę?
Tak, gdy każda krawędź liczy się tak samo: gdy BFS po raz pierwszy dociera do wierzchołka, używa najmniejszej możliwej liczby krawędzi. Dla krawędzi o różnych długościach użyj zamiast tego algorytmu Dijkstry.
Czym różni się BFS od DFS?
Przeszukiwanie wszerz używa kolejki i rozchodzi się równomiernie, pierścień po pierścieniu. Przeszukiwanie w głąb używa stosu (lub rekurencji) i podąża jedną ścieżką tak głęboko, jak się da, zanim się wycofa. BFS znajduje najkrótsze ścieżki w krawędziach; DFS nie, ale przydaje się do wykrywania cykli i sortowania topologicznego.
Jak szybkie jest przeszukiwanie wszerz?
Każdy wierzchołek zdejmuje z kolejki raz, a każdą krawędź sprawdza z obu końców, więc praca rośnie wraz z liczbą wierzchołków i krawędzi.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i jest przeszukiwany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora