Algorytm wyszukiwania wszerz (BFS) z PRZYKŁADEM

Co to jest algorytm BFS (wyszukiwanie wszerz)?

Przeszukiwanie wszerz (BFS) to algorytm służący do tworzenia wykresów danych, przeszukiwania drzew lub struktur. Pełna nazwa 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

1. Na różnych poziomach danych możesz oznaczyć dowolny węzeł jako węzeł początkowy lub początkowy, od którego rozpocznie się przechodzenie. BFS odwiedzi węzeł, oznaczy go jako odwiedzony i umieści w kolejce.
2. 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.
3. W podobny sposób analizowane są pozostałe najbliższe i nieodwiedzone węzły na grafie, oznaczane i dodawane do kolejki. Elementy te są usuwane z kolejki w momencie ich otrzymania i drukowane jako wynik.

Dlaczego potrzebujemy algorytmu BFS?

Istnieje wiele powodów, dla których warto wykorzystać algorytm BFS do przeszukiwania zbioru danych. Oto kilka najważniejszych aspektów, które sprawiają, że ten algorytm jest Twoim 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.

Można zatem powiedzieć, że wszystkie węzły sąsiadujące z bieżącym wierzchołkiem są odwiedzane i przemierzane w pierwszej iteracji. Do zaimplementowania działania algorytmu BFS wykorzystano prostą metodologię kolejkowania, która 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, należy dodać wierzchołek V do kolejki BFS.

Krok 3)

Rozpocznij przeszukiwanie BFS i po jego 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 na grafie, które sąsiadują z wierzchołkiem V.

Krok 6)

Dla każdego sąsiedniego wierzchołka, powiedzmy V1, w przypadku gdy nie został on jeszcze odwiedzony, należy dodać 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ąsiadujące i nieodwiedzone węzły są odwiedzane, oznaczane i wstawiane 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 – First In First Out) struktura danych jest używany przez BFS.
• Oznaczasz dowolny węzeł na wykresie jako korzeń i zaczynasz przeglądać dane od niego.
• BFS przechodzi przez wszystkie węzły w grafie i stale je usuwaping je jako ukończone.
• 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 powtarza się, aż do momentu, gdy wszystkie wierzchołki na grafie 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 łatwo utworzyć najkrótszą ścieżkę i minimalne drzewo rozpinające, aby przejść przez wszystkie wierzchołki grafu w najkrótszym możliwym czasie i z dużą dokładnością.
• Sieci P2P: BFS można wdrożyć w celu zlokalizowania wszystkich najbliższych lub sąsiednich węzłów w sieci peer-to-peer. Pozwoli to na szybsze znalezienie potrzebnych danych.
• 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.

FAQ