BFS vs DFS – różnica między nimi

Co to jest BFS?

BFS to algorytm, który służy do tworzenia wykresów danych lub przeszukiwania drzew lub przechodzenia przez struktury. Algorytm ten sprawnie odwiedza i oznacza wszystkie kluczowe węzły na wykresie w dokładny sposób wszerz.

Ten algorytm wybiera pojedynczy węzeł (punkt początkowy lub źródłowy) na grafie, a następnie odwiedza wszystkie węzły sąsiadujące z wybranym węzłem. Po odwiedzeniu i oznaczeniu węzła początkowego algorytm przechodzi do najbliższych nieodwiedzonych węzłów i analizuje je.

Po odwiedzeniu wszystkie węzły zostaną zaznaczone. Te iteracje są kontynuowane, dopóki wszystkie węzły grafu nie zostaną pomyślnie odwiedzone i oznaczone. Pełna forma BFS to przeszukiwanie wszerz.

Co to jest DFS?

DFS to algorytm służący do wyszukiwania lub przemierzania grafów lub drzew w kierunku w głąb. Wykonywanie algorytmu rozpoczyna się w węźle głównym i bada każdą gałąź przed cofnięciem się. Używa struktury danych stosu do zapamiętywania, pobierania kolejnego wierzchołka i rozpoczynania wyszukiwania za każdym razem, gdy w dowolnej iteracji pojawi się ślepy zaułek. Pełna forma DFS to przeszukiwanie w głąb.

Różnica między drzewem binarnym BFS i DFS

Oto ważne różnice między BFS i DFS.

BFS	DFS
BFS znajduje najkrótszą drogę do celu.	DFS schodzi na dół poddrzewa, a następnie cofa się.
Pełna forma BFS to wyszukiwanie wszerz.	Pełna forma DFS to przeszukiwanie w głąb.
Wykorzystuje kolejkę do śledzenia następnej lokalizacji do odwiedzenia.	Używa stosu, aby śledzić następną lokalizację do odwiedzenia.
BFS przemieszcza się zgodnie z poziomem drzewa.	DFS przemieszcza się w zależności od głębokości drzewa.
Jest realizowany przy użyciu 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.
Algorytm ten daje rozwiązanie najpłytszej ścieżki.	Algorytm ten nie gwarantuje rozwiązania najpłytszej ścieżki.
W BFS nie ma potrzeby cofania się.	Istnieje potrzeba cofnięcia się 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 zostanie znalezione rozwiązanie.	Jeśli nie znajdziesz żadnego celu, może nastąpić cofanie się węzła liścia.

Przykład BFS

W poniższym przykładzie BFS użyliśmy grafu mającego 6 wierzchołków.

Przykład 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ąsiednich i nieodwiedzonych węzłów jest odwiedzanych, oznaczanych i wstawianych do kolejki.

Krok 5)

Iteracje przechodzenia są powtarzane aż do odwiedzenia wszystkich węzłów.

Przykład DFS

W poniższym przykładzie DFS użyliśmy grafu niekierunkowego posiadającego 5 wierzchołków.

Krok 1)

Rozpoczęliśmy od wierzchołka 0. Algorytm rozpoczyna się od umieszczenia go na liście odwiedzonych i jednoczesnego umieszczenia wszystkich sąsiadujących z nim wierzchołków na liście struktura danych zwany stosem.

Krok 2)

Odwiedzisz element, który znajduje się na górze stosu, np. 1 i przejdziesz do sąsiednich węzłów. Dzieje się tak, ponieważ 0 zostało już odwiedzonych. 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 przechodzenie przez graf za pomocą algorytmu DFS.

Zastosowania BFS

Oto zastosowania 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 grafu w możliwie najkrótszym czasie i z dużą dokładnością.

Sieci P2P

BFS można wdrożyć, aby zlokalizować wszystkie najbliższe lub sąsiadujące węzły w sieci peer-to-peer. To pozwoli szybciej znaleźć wymagane dane.

Przeszukiwacze sieci

Wyszukiwarki lub 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.

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.

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 znajdziemy 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 wyszukiwania ścieżki między dwoma wierzchołkami.

Sortowanie topologiczne

Jest on używany głównie do planowania zadań z podanych zależności między grupą zadań. W informatyce jest używany w planowaniu instrukcji, serializacji danych, syntezie logicznej, określaniu kolejności zadań kompilacji.

Wyszukiwanie silnie spójnych komponentów grafu

Używa się go na grafie DFS, gdy istnieje ścieżka z każdego wierzchołka na wykresie do pozostałych pozostałych wierzchołków.

Rozwiązywanie zagadek z tylko jednym rozwiązaniem

Algorytm DFS można łatwo dostosować do wyszukiwania wszystkich rozwiązań labiryntu poprzez włączenie węzłów na istniejącej ścieżce do odwiedzanego zbioru.