Algorytm przeszukiwania wszerz (BFS)

Przeszukiwanie wszerz przypisuje dwie wartości każdemu wierzchołkowi $v$‍:

Jeśli nie istnieje ścieżka z wierzchołka początkowego do wierzchołka $v$‍, wtedy odległość przypisana wierzchołkowi $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$‍ od źródła, przed odwiedzinami wierzchołków o odległości $k+1$‍.

Wraz z powyższym przykładem, podajemy kroki oraz wizualizację do odtworzenia w każdy kroku:

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:

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:

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$‍ po których następują wierzchołki o odległości $k+1$‍. Właśnie w ten sposób zapewniamy, że odwiedzimy wszystkie wierzchołki o odległości $k$‍ zanim odwiedzimy wierzchołki o odległości $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.