Odwiedzone
W kolejce
Sprawdzone krawędzie

  • Bieżący
  • W kolejce
  • Odwiedzone
  • Ścieżka
Kliknięcie wierzchołka ustawia

Więcej o przeszukiwaniu wszerz

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

  1. Kliknij wierzchołek, aby uczynić go startem. Aby szukać ścieżki, przełącz kliknięcie na Cel i kliknij inny wierzchołek.
  2. 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.
  3. 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