Algorytm wyszukiwania w szerokości: przegląd, znaczenie i zastosowania

Wykresy są wszędzie wokół nas. Graf można traktować jako połączoną sieć węzłów i krawędzi. Twoi znajomi na Facebooku, Twoje kontakty na LinkedIn lub Twoi obserwatorzy na Twitterze/Instagramie tworzą Twój wykres społecznościowy. Podobnie, jeśli chcesz przejść z punktu A do punktu B, możesz to zrobić wieloma trasami, które można wizualizować na Mapach Google.

Wszystkie te liczne opcje trasy z punktu A do punktu B również tworzą wykres. Wykresy należą do najczęstszych struktur danych, które spotykamy zarówno w środowisku akademickim, jak i rzeczywistym, ponieważ są tak wszechobecne. Jedną z najczęstszych operacji, które można wykonać na grafie, jest przechodzenie przez graf.

Co to jest przechodzenie przez wykres?

Graph Traversal to metoda szybkiego i precyzyjnego odwiedzania każdego węzła na wykresie dokładnie raz. Jest to zaawansowany algorytm wyszukiwania grafów, który umożliwia wydrukowanie sekwencji odwiedzonych węzłów bez wpadania w nieskończoną pętlę. Istnieje wiele algorytmów przemierzania wykresów, takich jak wyszukiwanie według głębokości , wyszukiwanie według szerokości , algorytm Djikstry , algorytm gwiazdy A i inne.

W tym artykule zagłębimy się w algorytm „ Breadth First Search Algorithm ” lub BFS.

Struktura wykresu

Zanim przyjrzymy się dokładniej pod maską BFS, zapoznajmy się z niektórymi terminologiami dotyczącymi wykresów za pomocą powyższego wykresu:

Węzeł główny — węzeł, w którym rozpoczyna się proces przechodzenia. Dla uproszczenia możemy uznać A za węzeł główny.

Poziomy — poziom to zbiór wszystkich węzłów, które są w równej odległości od węzła głównego. Więc jeśli uznamy, że węzeł A jest na poziomie 0, węzły B i C są na poziomie 1, podczas gdy węzły D, E i F są na poziomie 2. Prostą heurystyką do określenia numeru poziomu węzła jest policzenie liczby krawędzi między wspomnianym węzłem a węzłem głównym. Zauważ, że działa to tylko wtedy, gdy zdefiniujesz węzeł główny na poziomie 0.

Węzeł nadrzędny — węzeł nadrzędny węzła to ten, który znajduje się jeden poziom nad nim i przylega do niego. Można go traktować jako węzeł, z którego pochodzi wspomniany węzeł. A jest węzłem macierzystym B i C.

Węzły podrzędne / podrzędne — węzły, które rozgałęziają się i sąsiadują z węzłem nadrzędnym. B i C są węzłami potomnymi A

Przeczytaj: 10 najlepszych technik wizualizacji danych

BFS to algorytm przechodzenia przez graf do wydajnego eksploracji drzewa lub grafu. Algorytm zaczyna się od węzła początkowego (węzła głównego), a następnie przechodzi do eksploracji wszystkich sąsiadujących z nim węzłów, w sposób najpierw wszerz, w przeciwieństwie do najpierw w głąb, który idzie w dół określonej gałęzi, aż do wszystkich węzłów w tej gałęzi są odwiedzane. Mówiąc prościej, przemierza wykres poziomowo, nie przesuwając się w dół poziomu, dopóki wszystkie węzły na tym poziomie nie zostaną odwiedzone i oznaczone.

Działa na zasadzie „pierwsze weszło-pierwsze wyszło” (FIFO) i jest zaimplementowane przy użyciu struktury danych kolejki. Po odwiedzeniu węzła jest on umieszczany w kolejce. Następnie jest rejestrowany i wszystkie jego węzły potomne są umieszczane w kolejce. Ten proces trwa, dopóki wszystkie węzły na wykresie nie zostaną odwiedzone i zarejestrowane.

Przyjrzyjmy się szczegółowym operacjom kolejkowym algorytmu BFS dla powyższego grafu:

() – oznacza kolejkę

[] – oznacza wydruk

1. Wstaw A do kolejki (a)
2. Wydrukuj A, wstaw B i C do kolejki (cb)[a]
3. Wydrukuj B, wstaw węzły podrzędne D i E do kolejki (edc)[ba]
4. Drukuj C, wstaw swój węzeł potomny F do kolejki (podaj)[cba]
5. Drukuj D, wstaw jego węzeł podrzędny do kolejki. Nie ma żadnych. (fe)[dcba]
6. Print E, którego węzeł podrzędny F został już wstawiony do kolejki. (f)[edcba]
7. Drukuj F. [fedcba]

Co sprawia, że ​​algorytm BFS jest ważny?

Istnieje wiele powodów, dla których warto wdrożyć BFS jako metodę szybkiego przeszukiwania ogromnych zbiorów danych. Niektóre z najważniejszych cech, które sprawiają, że jest to preferowany wybór dla programistów i inżynierów danych, to:

• BFS może skutecznie eksplorować wszystkie węzły na wykresie i znaleźć najkrótszą możliwą ścieżkę do eksploracji ich wszystkich.
• Liczba iteracji wymaganych do przebycia całego wykresu jest mniejsza niż w przypadku innych algorytmów wyszukiwania.
• Ponieważ jest implementowany przy użyciu kolejki, jego architektura jest solidna, niezawodna i elegancka.
• W porównaniu z innymi algorytmami dane wyjściowe BFS są dokładne i wolne od błędów.
• Iteracje BFS przebiegają płynnie, bez ryzyka wpadnięcia w nieskończoną pętlę.

Zamówienie: projekty wizualizacji danych, które można replikować

Zastosowania algorytmu BFS

Ze względu na swoją prostotę i łatwość konfiguracji algorytm BFS znalazł szerokie zastosowanie w różnych kluczowych sytuacjach rzeczywistych. Przyjrzyjmy się kilku znanym aplikacjom:

Roboty wyszukiwarek — spróbuj wyobrazić sobie świat bez Google i Bing. Nie możesz. Wyszukiwarki to kręgosłup internetu. A algorytm BFS jest podstawą wyszukiwarek. Jest to podstawowy algorytm używany do indeksowania stron internetowych. Algorytm rozpoczyna swoją podróż od strony źródłowej (węzła głównego), a następnie podąża za wszystkimi linkami na tej stronie źródłowej w szerokim zakresie. Każda strona internetowa może być traktowana jako niezależny węzeł na wykresie.

Nieważone przechodzenie przez wykres — BFS może zidentyfikować najkrótszą ścieżkę i minimalne drzewo opinające na wykresie nieważonym. Znalezienie najkrótszej trasy polega jedynie na znalezieniu ścieżki o najmniejszej liczbie krawędzi, do której BFS jest idealnie przystosowany. Może wykonać pracę, odwiedzając najmniejszą liczbę węzłów.

Nawigacja GPS – BFS wykorzystuje systemy GPS, aby wydobyć wszystkie możliwe sąsiednie lokalizacje z punktu początkowego, pomagając płynnie nawigować z punktu A do B.

Transmisja — sieć rozgłoszeniowa wykorzystuje pakiety jako jednostki do przenoszenia sygnałów i danych. Algorytm BFS steruje tymi pakietami, aby dotarły do ​​wszystkich węzłów w sieci, do której mają dotrzeć.

Sieci P2P — torrenty lub inne sieci udostępniania plików polegają na komunikacji P2P. BFS działa znakomicie, aby znaleźć najbliższe węzły, dzięki czemu transfer danych może nastąpić szybciej.

Przeczytaj także: Korzyści z wizualizacji danych

Wniosek

Ergo, algorytm Breadth First Search jest jednym z najważniejszych algorytmów współczesnego internetu. Mamy nadzieję, że ten blog będzie przydatnym punktem wyjścia w eksploracji algorytmu wyszukiwania.

Zalecamy wybranie PG Diploma in Data Science oferowanego przez IIIT Bangalore hostowanego na upGrad, ponieważ tutaj możesz uzyskać swoje pytania 1-1 z instruktorami kursu. Koncentruje się nie tylko na nauce teoretycznej, ale przywiązuje wagę do wiedzy praktycznej, która jest niezbędna, aby przygotować uczniów do stawienia czoła projektom w świecie rzeczywistym i zapewnić pierwszy indyjski certyfikat NASSCOM, który pomaga w zdobyciu dobrze płatnej pracy w Data Science.