Algorytm BFS(przeszukiwanie wszerz) służy do znajdowania najkrótszej ścieżki z jednego wierzchołka do wszystkich w grafie nieważonym lub o jednakowych wagach. Pierwszym pomysłem na algorytm może być przejście po wszystkich ścieżkach, ale to jest oczywiście za wolne. Rozwiązaniem tego problemu jest algorytm BFS.
Algorytm BFS polega na podzieleniu grafu na warstwy w taki sposób, że numer warstwy odpowiada za odległość z wierzchołka
startowego do wierzchołka z danej warstwy. Jak podzielić graf na warstwy? A bardzo prosto:
W warstwie zerowej jest wierzchołek startowy
W pierwszej warstwie są sąsiedzi wierzchołka startowego
W drugiej warstwie są jeszcze nieokreśleni sąsiedzi wierzchołków z warstwy pierwszej.
W x-tej warstwie są jeszcze niekreśleni sąsiedzi wierzchołków z warsty x-1.
Algorytm powtarzamy, aż żaden wierzchołek nie zostanie nam do rozpatrzenia.
Zasymulujmy algorytm BFS dla takiego grafu(zaczynając od wierzchołka 1):
W warstwie zerowej, skoro zaczynamy od 1 będzie wierzchołek 1.
W warstie pierwszej będą sąsiedzi 1, czyli 2 3 i 5.
W warstie drugiej będą nieodwiedzeni jeszcze sąsiedzi 2 3 i 5, czyli 4 6 i 7.
W warstwie trzeciej będą nieodwiedzeni jeszcze sąsiedzi 4 6 i 7, czyli 8
Tutaj zauważamy, że odwiedziliśmy już wszystkie wierzchołki, więc kończymy algorytm.
Algorytm BFS(przeszukiwanie wszerz) dla grida służy do znajdowania najkrótszej ścieżki z jednej komórki do wszystkich w gridzie. Pierwszym pomysłem na algorytm może być przejście po wszystkich ścieżkach, ale to jest oczywiście za wolne. Rozwiązaniem tego problemu jest algorytm BFS dla grida.
Algorytm BFS dla grida polega dokładnie na tym samym co zwykły algorytm BFS, tylko że zamiast grafu mamy prostokątną planszę - grida. Jako wierzchołki występują poszczególne komórki, a jako krawędzie - ścianki pomiędzy komórkami. Można niektóre ścianki/komórki zablokować, tylko trzeba będzie dodać odpowiednie ify 😉. Poniżej (w przykładzie i kodzie) przedstawiam wersję bez blokad ścianek i krawędzi.
Zasymulujmy algorytm BFS dla grida dla grida o wymiarach 3x2 (zaczynając z komórki 1, 1).
1 | 2 | 3 | |
1 | |||
2 |
1 | 2 | 3 | |
1 | 0 | 1 | 2 |
2 | 1 | 2 | 3 |