Co to jest algorytm BFS (wyszukiwanie wszerz)?
Przeszukiwanie wszerz (BFS) to algorytm, który jest używany do tworzenia wykresów danych lub wyszukiwania drzew lub przemierzających struktur. Pełna forma BFS to wyszukiwanie wszerz.
Algorytm skutecznie odwiedza i zaznacza wszystkie kluczowe węzły na wykresie w dokładny, szeroki sposób. Ten algorytm 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. Pamiętaj, że BFS uzyskuje dostęp do tych węzłów jeden po drugim.
Gdy algorytm odwiedza i zaznacza węzeł początkowy, przesuwa się w kierunku najbliższych nieodwiedzonych węzłów i analizuje je. Po odwiedzeniu wszystkie węzły są zaznaczane. Te iteracje są kontynuowane, dopóki wszystkie węzły wykresu nie zostaną pomyślnie odwiedzone i oznaczone.
W tym samouczku dotyczącym algorytmu dowiesz się:
- Co to jest algorytm BFS (wyszukiwanie wszerz)?
- Co to jest przemierzanie wykresów?
- Architektura algorytmu BFS
- Dlaczego potrzebujemy algorytmu BFS?
- Jak działa algorytm BFS?
- Przykładowy algorytm BFS
- Zasady algorytmu BFS
- Zastosowania algorytmu BFS
Co to jest przemierzanie wykresów?
Przechodzenie przez wykres jest powszechnie stosowaną metodologią lokalizowania położenia wierzchołka na wykresie. Jest to zaawansowany algorytm wyszukiwania, który potrafi szybko i precyzyjnie analizować wykres wraz z zaznaczaniem kolejności odwiedzanych wierzchołków. Ten proces umożliwia szybkie odwiedzanie każdego węzła na wykresie bez zamykania się w nieskończonej pętli.
Architektura algorytmu BFS
- Na różnych poziomach danych można oznaczyć dowolny węzeł jako węzeł początkowy lub początkowy, aby rozpocząć przemierzanie. BFS odwiedzi węzeł i oznaczy go jako odwiedzony i umieści go w kolejce.
- Teraz BFS odwiedzi najbliższe i nieodwiedzone węzły i oznaczy je. Te wartości są również dodawane do kolejki. Kolejka działa w modelu FIFO.
- W podobny sposób pozostałe najbliższe i nieodwiedzone węzły na wykresie są analizowane, zaznaczane i dodawane do kolejki. Te elementy są usuwane z kolejki w momencie odbioru i drukowane jako wynik.
Dlaczego potrzebujemy algorytmu BFS?
Istnieje wiele powodów, dla których warto skorzystać z algorytmu BFS do wyszukiwania zestawu danych. Oto niektóre z najważniejszych aspektów, które sprawiają, że ten algorytm jest Twoim pierwszym wyborem:
- BFS jest przydatne do analizowania węzłów na wykresie i konstruowania najkrótszej ścieżki przechodzenia przez nie.
- BFS może przechodzić przez wykres w najmniejszej liczbie iteracji.
- Architektura algorytmu BFS jest prosta i solidna.
- Wynik algorytmu BFS posiada wysoki poziom dokładności w porównaniu z innymi algorytmami.
- Iteracje BFS są płynne i nie ma możliwości, aby ten algorytm został złapany w problem nieskończonej pętli.
Jak działa algorytm BFS?
Przechodzenie przez wykres wymaga, aby algorytm odwiedzał, sprawdzał i / lub aktualizował każdy nieodwiedzony węzeł w strukturze drzewiastej. Przejścia przez wykres są klasyfikowane według kolejności, w jakiej odwiedzają węzły na wykresie.
Algorytm BFS rozpoczyna operację od pierwszego lub początkowego węzła na grafie i dokładnie ją przemierza. Po pomyślnym przejściu przez węzeł początkowy, następny nieprzekraczany wierzchołek na wykresie jest odwiedzany i oznaczany.
W związku z tym można powiedzieć, że wszystkie węzły sąsiadujące z bieżącym wierzchołkiem są odwiedzane i przemierzane w pierwszej iteracji. Do implementacji działania algorytmu BFS wykorzystywana jest prosta metodologia kolejkowania, która składa się z następujących kroków:
Krok 1)
Każdy wierzchołek lub węzeł na wykresie jest znany. Na przykład możesz oznaczyć węzeł jako V.
Krok 2)
W przypadku, gdy wierzchołek V nie jest dostępny, dodaj wierzchołek V do kolejki BFS
Krok 3)
Rozpocznij wyszukiwanie BFS i po zakończeniu zaznacz wierzchołek V jako odwiedzony.
Krok 4)
Kolejka BFS nadal nie jest pusta, dlatego usuń wierzchołek V wykresu z kolejki.
Krok 5)
Pobierz wszystkie pozostałe wierzchołki wykresu, które sąsiadują z wierzchołkiem V.
Krok 6)
Dla każdego sąsiedniego wierzchołka powiedzmy V1, na wypadek gdyby nie był jeszcze odwiedzany, dodaj V1 do kolejki BFS
Krok 7)
BFS odwiedzi V1 i oznaczy go jako odwiedzony i usunie z kolejki.
Przykładowy algorytm BFS
Krok 1)
Masz wykres siedmiu liczb z zakresu od 0 do 6.
Krok 2)
0 lub zero zostało oznaczone jako węzeł główny.
Krok 3)
0 jest odwiedzane, zaznaczane i wstawiane 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 do momentu odwiedzenia wszystkich węzłów.
Zasady algorytmu BFS
Oto ważne zasady korzystania z algorytmu BFS:
- Struktura danych kolejki (FIFO-First in First Out) jest używana przez BFS.
- Zaznaczasz dowolny węzeł na wykresie jako korzeń i zaczynasz przemierzać dane z niego.
- BFS przechodzi przez wszystkie węzły na wykresie i upuszcza je jako ukończone.
- BFS odwiedza sąsiedni nieodwiedzony węzeł, oznacza go jako zrobiony i wstawia do kolejki.
- Usuwa poprzedni wierzchołek z kolejki w przypadku, gdy nie zostanie znaleziony sąsiedni wierzchołek.
- Algorytm BFS wykonuje iterację, dopóki wszystkie wierzchołki wykresu nie zostaną pomyślnie przekroczone i oznaczone jako zakończone.
- Nie ma żadnych pętli spowodowanych przez BFS podczas przechodzenia przez dane z dowolnego węzła.
Zastosowania algorytmu BFS
Rzućmy okiem na niektóre z rzeczywistych aplikacji, w których implementacja algorytmu BFS może być bardzo skuteczna.
- Wykresy nieważone: algorytm BFS może łatwo utworzyć najkrótszą ścieżkę i minimalne drzewo rozpinające, aby odwiedzić wszystkie wierzchołki wykresu w jak najkrótszym czasie z dużą dokładnością.
- Sieci P2P: BFS można zaimplementować w celu zlokalizowania wszystkich najbliższych lub sąsiednich węzłów w sieci peer to peer. Pozwoli to szybciej znaleźć wymagane dane.
- Roboty sieciowe: wyszukiwarki lub roboty sieciowe mogą z łatwością budować wiele poziomów indeksów, korzystając z BFS. Implementacja BFS rozpoczyna się od źródła, którym 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.
- Rozgłaszanie sieciowe: pakiet rozgłaszany jest kierowany przez algorytm BFS, aby znaleźć i dotrzeć do wszystkich węzłów, dla których ma adres.
Podsumowanie
- Przechodzenie przez wykres to unikalny proces, który wymaga od algorytmu odwiedzenia, sprawdzenia i / lub aktualizacji każdego nieodwiedzonego węzła w strukturze drzewiastej. Algorytm BFS działa na podobnej zasadzie.
- Algorytm jest przydatny do analizy węzłów na grafie i konstruowania najkrótszej ścieżki przejścia przez nie.
- Algorytm przechodzi przez wykres w najmniejszej liczbie iteracji i w najkrótszym możliwym 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 są umieszczane w kolejce przez BFS. Kolejka działa na zasadzie „pierwsze weszło-pierwsze wyszło”. W związku z tym element umieszczony na wykresie jako pierwszy jest usuwany jako pierwszy i w rezultacie drukowany.
- Algorytm BFS nigdy nie 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 sieciowe i transmisje sieciowe.