Wprowadzenie do algorytmu BFS
Aby uzyskać dostęp do danych i efektywnie nimi zarządzać, można je przechowywać i organizować w specjalnym formacie zwanym strukturą danych. Istnieje wiele struktur danych, takich jak stos, tablica, lista połączona, kolejki, drzewa i wykresy itp. W liniowych strukturach danych, takich jak stos, tablica, lista połączona i kolejka, dane są uporządkowane w kolejności liniowej, natomiast w liniowe struktury danych, takie jak drzewa i wykresy, dane są uporządkowane hierarchicznie, a nie w sekwencji. Wykres jest nieliniową strukturą danych, która ma węzły i krawędzie. Węzły na wykresie można również określać jako wierzchołki, których liczba jest skończona, a krawędzie są liniami łączącymi dowolne dwa węzły.
Na powyższym wykresie wierzchołki można przedstawić jako V = (A, B, C, D, E), a krawędzie można zdefiniować jako
E = (AB, AC, CD, BE)
Co to jest algorytm BFS?
Zasadniczo istnieją dwa algorytmy wykorzystywane do przechodzenia przez wykres. Są to algorytmy BFS (pierwsze wyszukiwanie) i DFS (pierwsze wyszukiwanie). Przemieszczanie wykresu odwiedza dokładnie jeden wierzchołek lub węzeł i krawędź, w ściśle określonej kolejności. Ponadto bardzo ważne jest, aby śledzić wierzchołki, które zostały odwiedzone, aby ten sam wierzchołek nie był dwukrotnie przemieszczany. W algorytmie Breath First Search przejście odbywa się od wybranego węzła lub węzła źródłowego, a przejście odbywa się przez węzły bezpośrednio podłączone do węzła źródłowego. Mówiąc prościej, w algorytmie BFS należy najpierw przesunąć poziomo i przejść przez bieżącą warstwę, a następnie przejść do następnej warstwy.
Jak działa algorytm BFS?
Weźmy przykład poniższego wykresu.
Ważnym zadaniem jest znalezienie najkrótszej ścieżki na wykresie podczas przechodzenia przez węzły. Kiedy przechodzimy przez wykres, wierzchołek przechodzi ze stanu nieodkrytego do stanu odkrytego i ostatecznie zostaje całkowicie odkryty. Należy zauważyć, że w pewnym momencie można utknąć podczas przechodzenia przez wykres, a węzeł można odwiedzić dwukrotnie. Możemy więc zastosować metodę oznaczania węzłów po zmianie stanu bycia nieodkrytym na całkowite wykrycie.
Na poniższym obrazku widać, że węzły można oznaczyć na wykresach, gdy zostaną całkowicie odkryte przez oznaczenie ich na czarno. Możemy zacząć od węzła źródłowego, a gdy przejście przechodzi przez każdy węzeł, można je oznaczyć do zidentyfikowania.
Podróż rozpoczyna się od wierzchołka, a następnie dociera do krawędzi wychodzących. Gdy krawędź przechodzi do nieodkrytego wierzchołka, jest oznaczona jako odkryta. Ale kiedy krawędź przechodzi do całkowicie odkrytego lub odkrytego wierzchołka, jest ignorowana.
W przypadku grafu ukierunkowanego każda krawędź jest odwiedzana raz, a dla wykresu niekierowanego jest odwiedzana dwa razy, tj. Raz podczas odwiedzania każdego węzła. Algorytm, który należy zastosować, jest ustalany na podstawie sposobu przechowywania wykrytych wierzchołków. W algorytmie BFS kolejka jest używana tam, gdzie najstarszy wierzchołek jest wykrywany jako pierwszy, a następnie propagowany przez warstwy od wierzchołka początkowego.
Kroki są wykonywane dla algorytmu BFS
Poniższe kroki są wykonywane dla algorytmu BFS.
- Na danym wykresie zacznijmy od wierzchołka, tj. Na powyższym schemacie jest to węzeł 0. Poziom, na którym ten wierzchołek jest obecny, można określić jako Warstwę 0.
- Następnym krokiem jest znalezienie wszystkich innych wierzchołków, które sąsiadują z początkowym wierzchołkiem, tj. Węzłem 0 lub są bezpośrednio z niego dostępne. Następnie możemy oznaczyć te sąsiadujące wierzchołki, aby były obecne w warstwie 1.
- Możliwe jest dojście do tego samego wierzchołka dzięki pętli na wykresie. Powinniśmy więc podróżować tylko do tych wierzchołków, które powinny znajdować się w tej samej warstwie.
- Następnie zaznaczany jest wierzchołek macierzysty bieżącego wierzchołka, w którym się znajdujemy. To samo należy wykonać dla wszystkich wierzchołków w warstwie 1.
- Następnie następnym krokiem jest znalezienie wszystkich tych wierzchołków, które są pojedynczą krawędzią od wszystkich wierzchołków znajdujących się w warstwie 1. Nowy zestaw wierzchołków będzie w warstwie 2.
- Powyższy proces powtarza się do momentu przejścia wszystkich węzłów.
Przykład:
Weźmy przykład poniższego wykresu i zrozummy, jak działa algorytm BFS. Zasadniczo w algorytmie BFS kolejka służy do umieszczania w kolejce węzłów podczas przechodzenia przez węzły.
Na powyższym wykresie najpierw należy odwiedzić węzeł 0, a ten węzeł jest umieszczony w kolejce do poniższej kolejki:
Po wizycie w węźle 0 sąsiedni węzeł 0, 1 i 2 zostaje umieszczony w kolejce. Kolejkę można przedstawić w następujący sposób: 
Następnie odwiedzony zostanie pierwszy węzeł w kolejce, który jest 2. Po odwiedzeniu węzła 2 kolejkę można przedstawić w następujący sposób:
Po wizycie w węźle 2, kolejka 5 zostanie umieszczona w kolejce, a ponieważ nie ma nieodwiedzonych sąsiednich węzłów dla węzła 5, mimo że kolejka 5 jest umieszczona w kolejce, ale nie będzie odwiedzana dwukrotnie.
Następnie pierwszy węzeł w kolejce to 1, który będzie odwiedzany. Sąsiadujące węzły 3 i 4 są umieszczone w kolejce. Kolejka jest przedstawiona poniżej
Następnie pierwszym węzłem w kolejce jest 5, a dla tego węzła nie ma już nieodwiedzonych sąsiednich węzłów. To samo dotyczy węzłów 3 i 4, dla których nie ma już innych nieodwiedzonych sąsiednich węzłów.
Tak więc wszystkie węzły są przemieszczane i kolejka staje się pusta.
Wniosek
Algorytm wyszukiwania szerokości ma kilka zalet, które go polecają. Jedną z wielu aplikacji algorytmu BFS jest obliczenie najkrótszej ścieżki. Jest również wykorzystywany w sieci do znajdowania sąsiednich węzłów i można go znaleźć w serwisach społecznościowych, w transmisji sieciowej i śmieciach. Użytkownicy muszą zrozumieć wymagania i wzorzec danych, aby móc je wykorzystać w celu uzyskania lepszej wydajności.
Polecane artykuły
To był przewodnik po algorytmie BFS. Tutaj omawiamy koncepcję, działanie, kroki i przykład wydajności w algorytmie BFS. Możesz także przejrzeć nasze inne Sugerowane artykuły, aby dowiedzieć się więcej -
- Co to jest Chciwy Algorytm?
- Algorytm śledzenia promieni
- Algorytm podpisu cyfrowego
- Co to jest Java Hibernacja?
- Kryptografia podpisów cyfrowych
- BFS VS DFS | 6 najważniejszych różnic dzięki infografikom