Algorytm przeszukiwania wszerz (BFS)

Przeszukiwanie wszerz przypisuje dwie wartości każdemu wierzchołkowi v v :
  • Odległość, czyli minimalną liczbę krawędzi na drodze z dowolnego wierzchołka do wierzchołka v v .
  • Przodka wierzchołka v v na najkrótszej ścieżce z wierzchołka początkowego. Przodek wierzchołka początkowego przyjmuje jakąś specjalną wartość, np. null, informującą o tym, że wierzchołek początkowy nie ma przodka.
Jeśli nie istnieje ścieżka z wierzchołka początkowego do wierzchołka v v , wtedy odległość przypisana wierzchołkowi v v jest równa nieskończoności, a przodek tego wierzchołka przyjmuje taką samą wartość specjalną, jak przodek wierzchołka początkowego.
Na przykład, tutaj jest nieskierowany graf z ośmioma wierzchołkami, ponumerowanymi od 0 do 7. Numery wierzchołków są narysowane powyżej lub poniżej wierzchołków. Wewnątrz każdego wierzchołka są dwie liczby: jego odległość od wierzchołka początkowego, którym jest wierzchołek 3, oraz jego przodek wzdłuż najkrótszej ścieżki do wierzchołka 3. Myślnik w wierzchołku 3 oznacza wartość specjalną, null:
W BFS, początkowo każdemu wierzchołkowi przypisujemy odległość oraz przodka, równe wartości specjalnej (null). Zaczynamy przeszukiwanie od wierzchołka początkowego, tzw. źródła i przypisujemy mu odległość równą 0. Następnie odwiedzamy wszystkich sąsiadów źródła i każdemu z nich przypisujemy odległość równą 1 oraz ustawiamy wartość przodka równą źródłu. Następnie odwiedzamy wszystkich sąsiadów tych wierzchołków, których odległość wynosi 1 i które nie były jeszcze odwiedzone, i nadajemy każdemu z tych wierzchołków odległość równą 2 oraz przypisujemy przodkowi wartość wierzchołka, z którego odwiedziliśmy dany wierzchołek. Postępujemy tak dopóki wszystkie wierzchołki osiągalne z wierzchołka początkowego nie zostały odwiedzone, zawsze odwiedzając wszystkie wierzchołki o odległości k k od źródła, przed odwiedzinami wierzchołków o odległości k+1 k+1 .
Wraz z powyższym przykładem, podajemy kroki oraz wizualizację do odtworzenia w każdy kroku:
  • Rozpocznij poprzez odwiedzenie wierzchołka 3, źródła, ustawiając jego odległość na 0.
  • Następnie odwiedź wierzchołki 2 i 6, ustawiając ich odległość na 1 i ich przodka na wierzchołek 3.
  • Rozpocznij odwiedzanie z wierzchołków o odległości 1 od źródła, zaczynając od wierzchołka 2. Z wierzchołka 2, odwiedź wierzchołki 4 i 5, ustawiając ich odległość na 2 i ich przodka na wierzchołek 2. Nie odwiedzaj wierzchołka 3, ponieważ on już został odwiedzony wcześniej.
  • Z wierzchołka 6, nie odwiedzaj wierzchołka 5, ponieważ on został właśnie odwiedzony z wierzchołka 2, i nie odwiedzaj również wierzchołka 3.
  • Teraz rozpocznij odwiedzanie z wierzchołków o odległości 2 od źródła. Zacznij odwiedzać z wierzchołka 4. Wierzchołek 2 został już odwiedzony. Odwiedź wierzchołek 1, ustaw jego odległość na 3 i jego przodka na 4.
  • Z wierzchołka 5, nie odwiedzaj żadnego z jego sąsiadów, ponieważ oni zostali już odwiedzeni wcześniej.
  • Teraz rozpocznij odwiedzanie z wierzchołków o odległości 3 od źródła. Jedynym takim wierzchołkiem jest wierzchołek 1. Jego sąsiedzi, wierzchołki 4 i 5, zostali już odwiedzeni. Ale wierzchołek 0 jeszcze nie. Odwiedź wierzchołek 0, ustawiając jego odległość na 4 i jego przodka na wierzchołek 1.
  • Teraz rozpocznij odwiedzanie z wierzchołków o odległości 4 od źródła. Taki jest tylko wierzchołek 0, a jego sąsiad, wierzchołek 1, został już odwiedzony. Zakończyliśmy!
Zauważ, że ponieważ nie istnieje ścieżka z wierzchołka 3 do wierzchołka 7, przeszukiwanie nigdy nie dociera do wierzchołka 7. Jego odległość i przodek pozostają niezmienione, zachowując ich początkową wartość null.
Nasuwa się kilka pytań. Jednym z nich jest to, jak określić czy wierzchołek został już odwiedzony. To proste: odległość wierzchołka jest równa null dopóki nie został on odwiedzony, bo w tym momencie przypisywana zostaje jego odległość. Stąd, gdy badamy sąsiadów danego wierzchołka, odwiedzamy jedynie sąsiadów, których odległość jest obecnie równa null.
Kolejnym pytaniem jest to, jak śledzić, które wierzchołki zostały już odwiedzone ale jeszcze nie rozpoczynaliśmy z nich odwiedzania. Używamy kolejki, która jest strukturą danych umożliwiającą nam wstawianie i usuwanie elementów, gdzie element usuwany jest zawsze tym, który był w kolejce najdłużej. Nazywamy to zachowanie pierwsze wchodzi, pierwsze wychodzi. Kolejka obsługuje trzy operacje:
  • enqueue(obj) wstawia obiekt do kolejki.
  • dequeue() usuwa z kolejki obiekt, który był najdłużej w kolejce, zwracając jednocześnie ten obiekt.
  • isEmpty() zwraca true jeśli kolejka obecnie nie zawiera żadnych obiektów, i false jeśli kolejka zawiera przynajmniej jeden obiekt.
Podczas gdy odwiedzamy wierzchołek po raz pierwszy, wstawiamy go do kolejki. Na początku, wstawiamy źródło do kolejki ponieważ to jest zawsze pierwszy wierzchołek, który odwiedzamy. Aby zdecydować, który wierzchołek odwiedzić w następnym kroku, wybieramy wierzchołek, który był w kolejce najdłużej i usuwamy go z kolejki—innymi słowy, używamy wierzchołka, który jest zwrócony z dequeue(). Patrząc na nasz przykładowy graf, tutaj podajemy jak wygląda kolejka po każdym kroku, plus poprzednia wizualizacja pokazująca również stan kolejki:
  • Początkowo, kolejka zawiera tylko wierzchołek 3 z odległością równą 0.
  • Usuń, poprzez wywołanie dequeue, wierzchołek 3, i wstaw, poprzez wywołanie enqueue, wierzchołki 2 i 6, oba z z odległością równą 1. Kolejka w tym momencie zawiera wierzchołek 2 z odległością 1 i wierzchołek 6 z odległością 1.
  • Usuń z kolejki wierzchołek 2, i wstaw wierzchołek 4 i 5, oba z odległością równą 2. Kolejka w tym momencie zawiera wierzchołek 6 z odległością 1, wierzchołek 4 z odległością 2 i wierzchołek 5 z odległością 2.
  • Usuń z kolejki wierzchołek 6, i nie wstawiaj innych wierzchołków. Kolejka teraz zawiera wierzchołek 4 z odległością 2 i wierzchołek 5 z odległością 2.
  • Usuń z kolejki wierzchołek 4, i dodaj do kolejki wierzchołek 1 z odległością 3. Kolejka teraz zawiera wierzchołek 5 z odległością 2 i wierzchołek 1 z odległością 3.
  • Usuń z kolejki wierzchołek 5, i nie wstawiaj żadnych innych wierzchołków. Kolejka zawiera teraz jedynie wierzchołek 1 z odległością 3.
  • Usuń z kolejki wierzchołek 1, i dodaj do kolejki wierzchołek 0 z odległością 4. Kolejka teraz zawiera jedynie wierzchołek 0 z odległością 4.
  • Usuń z kolejki wierzchołek 0 i nie wstawiaj do kolejki innych wierzchołków. Kolejka jest teraz pusta. Ponieważ kolejka jest pusta, przeszukiwanie grafu wszerz kończy się.
Zauważ, że w każdym momencie, albo kolejka zawiera wszystkie wierzchołki z tą samą odległością, albo zawiera wierzchołki z odległością k k po których następują wierzchołki o odległości k+1 k+1 . Właśnie w ten sposób zapewniamy, że odwiedzimy wszystkie wierzchołki o odległości k k zanim odwiedzimy wierzchołki o odległości k+1 k+1 .

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Ładowanie