Co to jest BFS?
BFS to algorytm używany do tworzenia wykresów danych lub przeszukiwania drzew lub przemierzających struktur. 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. 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. Pełna forma BFS to wyszukiwanie wszerz.
W tym BSF Vs. Samouczek dotyczący drzewa binarnego DFS, dowiesz się:
- Co to jest BFS?
- Co to jest DFS?
- Przykład BFS
- Przykład DFS
- Różnica między drzewem binarnym BFS i DFS
- Zastosowania BFS
- Zastosowania DFS
Co to jest DFS?
DFS to algorytm do znajdowania lub przechodzenia przez wykresy lub drzewa w kierunku w głąb. Wykonywanie algorytmu rozpoczyna się w węźle głównym i bada każdą gałąź przed cofnięciem. Używa struktury danych stosu do zapamiętania, uzyskania kolejnego wierzchołka i rozpoczęcia wyszukiwania, gdy tylko ślepy zaułek pojawi się w dowolnej iteracji. Pełna forma DFS to wyszukiwanie w głąb.
Przykład BFS
W poniższym przykładzie DFS użyliśmy grafu mającego 6 wierzchołków.
Przykład 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.
Przykład DFS
W poniższym przykładzie DFS użyliśmy grafu nie skierowanego, który ma 5 wierzchołków.
Krok 1)
Zaczęliśmy od wierzchołka 0. Algorytm rozpoczyna od umieszczenia go na liście odwiedzonych i jednoczesnego umieszczenia wszystkich sąsiednich wierzchołków w strukturze danych zwanej stosem.
Krok 2)
Odwiedzisz element znajdujący się na szczycie stosu, na przykład 1 i przejdziesz do jego sąsiednich węzłów. Dzieje się tak, ponieważ 0 zostało już odwiedzone. Dlatego odwiedzamy wierzchołek 2.
Krok 3)
Wierzchołek 2 ma nieodwiedzony pobliski wierzchołek w 4. Dlatego dodajemy go do stosu i odwiedzamy.
Krok 4)
Na koniec odwiedzimy ostatni wierzchołek 3, nie ma on żadnych nieodwiedzonych sąsiednich węzłów. Zakończyliśmy przeglądanie wykresu za pomocą algorytmu DFS.
Różnica między drzewem binarnym BFS i DFS
| BFS | DFS |
| BFS znajduje najkrótszą ścieżkę do celu. | DFS przechodzi na koniec poddrzewa, a następnie cofa. |
| Pełna forma BFS to Breadth-First Search. | Pełną formą DFS jest wyszukiwanie w głębi. |
| Używa kolejki, aby śledzić następną lokalizację do odwiedzenia. | Używa stosu, aby śledzić następną lokalizację do odwiedzenia. |
| BFS porusza się zgodnie z poziomem drzewa. | DFS porusza się zgodnie z głębokością drzewa. |
| Jest realizowany za pomocą listy FIFO. | Jest realizowany przy użyciu listy LIFO. |
| Wymaga więcej pamięci w porównaniu do DFS. | Wymaga mniej pamięci w porównaniu do BFS. |
| Ten algorytm zapewnia najcieplejsze rozwiązanie ścieżki. | Ten algorytm nie gwarantuje rozwiązania najpłytszej ścieżki. |
| Nie ma potrzeby cofania się w BFS. | Istnieje potrzeba wycofania w DFS. |
| Nigdy nie możesz zostać uwięziony w skończonych pętlach. | Możesz zostać uwięziony w nieskończonych pętlach. |
| Jeśli nie znajdziesz żadnego celu, może być konieczne rozwinięcie wielu węzłów, zanim rozwiązanie zostanie znalezione. | Jeśli nie znajdziesz żadnego celu, może wystąpić cofanie się węzła liścia. |
Zastosowania BFS
Oto aplikacje BFS:
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 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 równorzędnej. Pozwoli to szybciej znaleźć wymagane dane.
Roboty internetowe:
Wyszukiwarki lub roboty sieciowe mogą łatwo budować wiele poziomów indeksów, stosując 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.
Transmisja sieciowa:
Rozgłaszany pakiet jest kierowany przez algorytm BFS, aby znaleźć i dotrzeć do wszystkich węzłów, dla których ma adres.
Zastosowania DFS
Oto ważne zastosowania DFS:
Wykres ważony:
Na wykresie ważonym przechodzenie przez wykres DFS generuje drzewo najkrótszej ścieżki i minimalne drzewo rozpinające.
Wykrywanie cyklu na wykresie:
Wykres ma cykl, jeśli podczas DFS znaleźliśmy tylną krawędź. Dlatego powinniśmy uruchomić DFS dla wykresu i sprawdzić tylne krawędzie.
Znalezienie drogi:
Możemy specjalizować się w algorytmie DFS do przeszukiwania ścieżki między dwoma wierzchołkami.
Sortowanie topologiczne:
Służy głównie do planowania zadań na podstawie określonych zależności w grupie zadań. W informatyce znajduje zastosowanie w szeregowaniu instrukcji, serializacji danych, syntezie logicznej, określaniu kolejności zadań kompilacji.
Wyszukiwanie silnie połączonych składników wykresu:
Jest używany na wykresie DFS, gdy istnieje ścieżka od każdego wierzchołka wykresu do innych pozostałych wierzchołków.
Rozwiązywanie zagadek za pomocą tylko jednego rozwiązania:
Algorytm DFS można łatwo dostosować do wyszukiwania wszystkich rozwiązań labiryntu, włączając węzły na istniejącej ścieżce w odwiedzanym zestawie.
KLUCZOWE RÓŻNICE:
- BFS znajduje najkrótszą ścieżkę do miejsca docelowego, podczas gdy DFS przechodzi na dół poddrzewa, a następnie cofa.
- Pełna forma BFS to przeszukiwanie wszerz, podczas gdy pełna forma DFS to przeszukiwanie wszerz.
- BFS korzysta z kolejki, aby śledzić następną lokalizację do odwiedzenia. podczas gdy DFS używa stosu do śledzenia następnej lokalizacji do odwiedzenia.
- BFS porusza się zgodnie z poziomem drzewa, podczas gdy DFS porusza się zgodnie z głębokością drzewa.
- BFS jest zaimplementowany przy użyciu listy FIFO, natomiast DFS jest zaimplementowany przy użyciu listy LIFO.
- W BFS nigdy nie możesz zostać uwięziony w skończonych pętlach, podczas gdy w DFS możesz zostać uwięziony w nieskończonych pętlach.