Algorytm wyszukiwania wszerz (BFS) z PRZYKŁADEM

Co to jest algorytm BFS (wyszukiwanie wszerz)?

Przeszukiwanie wszerz (BFS) to algorytm, który jest używany do tworzenia wykresów danych lub przeszukiwania drzew lub przechodzenia przez struktury. Pełna forma BFS to przeszukiwanie wszerz.

Algorytm skutecznie odwiedza i oznacza wszystkie kluczowe węzły w grafie w dokładny sposób wszerz. Ten algorytm wybiera pojedynczy węzeł (punkt początkowy lub źródłowy) w grafie, a następnie odwiedza wszystkie węzły sąsiadujące z wybranym węzłem. Pamiętaj, że BFS uzyskuje dostęp do tych węzłów jeden po drugim.

Gdy algorytm odwiedzi i oznaczy węzeł początkowy, przechodzi do najbliższych nieodwiedzonych węzłów i analizuje je. Po odwiedzeniu wszystkie węzły są oznaczane. Te iteracje są kontynuowane, aż wszystkie węzły grafu zostaną pomyślnie odwiedzone i oznaczone.

Co to jest przechodzenie przez graf?

Przechodzenie przez graf jest powszechnie stosowaną metodologią lokalizowania pozycji wierzchołków na wykresie. Jest to zaawansowany algorytm wyszukiwania, który pozwala szybko i precyzyjnie analizować graf wraz z zaznaczaniem kolejności odwiedzanych wierzchołków. Ten proces umożliwia szybkie odwiedzanie każdego węzła na wykresie bez wpadania w nieskończoną pętlę.

Architektura algorytmu BFS

Na różnych poziomach danych możesz oznaczyć dowolny węzeł jako węzeł początkowy lub początkowy, aby rozpocząć przemierzanie. BFS odwiedzi węzeł, oznaczy go jako odwiedzony i umieści w kolejce.
Teraz BFS odwiedzi najbliższe i nieodwiedzone węzły i je oznaczy. Te wartości są również dodawane do kolejki. Kolejka działa na modelu FIFO.
W podobny sposób pozostałe najbliższe i nieodwiedzone węzły na wykresie są analizowane, oznaczane i dodawane do kolejki. Te elementy są usuwane z kolejki jako otrzymane i drukowane jako wynik.

Dlaczego potrzebujemy algorytmu BFS?

Istnieje wiele powodów, dla których warto wykorzystać algorytm BFS do wyszukiwania zestawu danych. Oto niektóre z najważniejszych aspektów, które sprawiają, że ten algorytm jest pierwszym wyborem:

BFS jest przydatny do analizy węzłów w grafie i konstruowania najkrótszej ścieżki przejścia przez nie.
BFS może przechodzić przez wykres w najmniejszej liczbie iteracji.
Architektura algorytmu BFS jest prosta i niezawodna.
Wynik algorytmu BFS charakteryzuje się wysokim poziomem dokładności w porównaniu z innymi algorytmami.
Iteracje BFS przebiegają płynnie i nie ma możliwości, aby algorytm wplątał się w problem z nieskończoną pętlą.

Jak działa algorytm BFS?

Przechodzenie przez graf wymaga od algorytmu odwiedzania, sprawdzania i/lub aktualizowania każdego pojedynczego nieodwiedzonego węzła w strukturze przypominającej drzewo. Przejścia po grafie są klasyfikowane według kolejności odwiedzania węzłów na wykresie.

Algorytm BFS rozpoczyna operację od pierwszego lub początkowego węzła w grafie i przechodzi przez niego dokładnie. Po pomyślnym przejściu przez węzeł początkowy, odwiedzany i oznaczany jest następny nieprzebyty wierzchołek w grafie.

Stąd można powiedzieć, że wszystkie węzły sąsiadujące z bieżącym wierzchołkiem są odwiedzane i przemierzane w pierwszej iteracji. Prosta metodologia kolejki jest wykorzystywana do implementacji działania algorytmu BFS i składa się z następujących kroków:

Krok 1)

Każdy wierzchołek lub węzeł grafu jest znany. Na przykład możesz oznaczyć węzeł jako V.

Krok 2)

W przypadku braku dostępu do wierzchołka V, dodaj wierzchołek V do kolejki BFS

Krok 3)

Rozpocznij wyszukiwanie BFS, a po zakończeniu oznacz wierzchołek V jako odwiedzony.

Krok 4)

Kolejka BFS nadal nie jest pusta, stąd usuń wierzchołek V grafu z kolejki.

Krok 5)

Pobierz wszystkie pozostałe wierzchołki grafu, które sąsiadują z wierzchołkiem V

Krok 6)

Dla każdego sąsiadującego wierzchołka powiedzmy V1, w przypadku, gdy nie jest jeszcze odwiedzony, dodaj V1 do kolejki BFS

Krok 7)

BFS odwiedzi V1, oznaczy ją jako odwiedzoną i usunie z kolejki.

Przykładowy algorytm BFS

Krok 1)

Masz wykres siedmiu liczb od 0 do 6.

Krok 2)

Jako węzeł główny oznaczono 0 lub zero.

Krok 3)

0 jest odwiedzany, zaznaczany i wstawiany do struktury danych kolejki.

Krok 4)

Pozostałe 0 sąsiednich i nieodwiedzonych węzłów jest odwiedzanych, oznaczanych i wstawianych do kolejki.

Krok 5)

Iteracje przechodzenia są powtarzane aż do odwiedzenia wszystkich węzłów.

Zasady algorytmu BFS

Oto ważne zasady korzystania z algorytmu BFS:

Kolejka (FIFO – pierwsze weszło, pierwsze wyszło) struktura danych jest używany przez BFS.
Zaznaczasz dowolny węzeł na wykresie jako główny i zaczynasz przeglądać z niego dane.
BFS przechodzi przez wszystkie węzły na wykresie i usuwa je po ukończeniu.
BFS odwiedza sąsiedni nieodwiedzony węzeł, oznacza go jako wykonany i wstawia do kolejki.
Usuwa poprzedni wierzchołek z kolejki w przypadku, gdy nie zostanie znaleziony żaden sąsiedni wierzchołek.
Algorytm BFS iteruje, aż wszystkie wierzchołki grafu zostaną pomyślnie przebyte i oznaczone jako ukończone.
Nie ma żadnych pętli spowodowanych przez BFS podczas przechodzenia danych z dowolnego węzła.

Zastosowania algorytmu BFS

Przyjrzyjmy się niektórym z rzeczywistych zastosowań, w których implementacja algorytmu BFS może być bardzo skuteczna.

Wykresy nieważone: Algorytm BFS może z łatwością utworzyć najkrótszą ścieżkę i minimalne drzewo rozpinające, aby odwiedzić wszystkie wierzchołki grafu w możliwie najkrótszym czasie i z dużą dokładnością.
Sieci P2P: BFS można wdrożyć, aby zlokalizować wszystkie najbliższe lub sąsiadujące węzły w sieci peer-to-peer. To pozwoli szybciej znaleźć wymagane dane.
Roboty indeksujące: Wyszukiwarki i roboty indeksujące mogą z łatwością tworzyć wiele poziomów indeksów, korzystając z BFS. Implementacja BFS rozpoczyna się od źródła, jakim jest strona internetowa, a następnie odwiedza wszystkie linki z tego źródła.
Systemy nawigacji: BFS może pomóc znaleźć wszystkie sąsiednie lokalizacje z lokalizacji głównej lub źródłowej.
Transmisja sieciowa: Rozgłaszany pakiet jest kierowany przez algorytm BFS w celu znalezienia i dotarcia do wszystkich węzłów, dla których ma adres.

Podsumowanie

Przechodzenie przez graf to unikalny proces, który wymaga od algorytmu odwiedzenia, sprawdzenia i/lub aktualizacji każdego pojedynczego nieodwiedzonego węzła w strukturze przypominającej drzewo. Algorytm BFS działa na podobnej zasadzie.
Algorytm jest przydatny do analizy węzłów w grafie i konstruowania najkrótszej ścieżki przejścia przez nie.
Algorytm przemierza graf w najmniejszej liczbie iteracji i w możliwie najkrótszym czasie.
BFS wybiera pojedynczy węzeł (punkt początkowy lub źródłowy) na wykresie, a następnie odwiedza wszystkie węzły sąsiadujące z wybranym węzłem. BFS uzyskuje dostęp do tych węzłów jeden po drugim.
Odwiedzone i zaznaczone dane umieszczane są w kolejce przez BFS. Kolejka działa na zasadzie „pierwszy weszł, pierwszy wyszedł”. Zatem element umieszczony na wykresie jako pierwszy jest usuwany jako pierwszy i w rezultacie drukowany.
Algorytm BFS nigdy nie może dać się złapać w nieskończoną pętlę.
Ze względu na wysoką precyzję i solidną implementację, BFS jest używany w wielu rzeczywistych rozwiązaniach, takich jak sieci P2P, roboty indeksujące i transmisje sieciowe.