BFS vs DFS: poznaj różnicę

Co to jest BFS ?

BFS to algorytm, który jest używany do tworzenia wykresów danych lub wyszukiwania 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 BFS a drzewem binarnym DFS
• Zastosowania BFS
• Zastosowania DFS

Co to jest DFS?

DFS to algorytm 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 grafu mającego 6 wierzchołków.

Przykład BFS

Krok 1)

Masz wykres siedmiu liczb z przedziału od 0 do 6.

Krok 2)

0 lub zero zostało zaznaczone jako węzeł główny.

Krok 3)

0 odwiedzonych, oznaczonych i wstawione do struktury danych kolejki.

Krok 4)

Pozostało 0 sąsiadujących i nieodwiedzonych węzły są odwiedzane, oznaczane i wstawiane do kolejki.

Krok 5)

Iteracje przechodzenia są powtarzane do wszystkie węzły są odwiedzane.

Przykład DFS

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

Krok 1)

Zaczęliśmy od wierzchołka 0. Algorytm zaczyna się od umieszczenia go na liście odwiedzonych i jednoczesnego umieszczenia wszystkich sąsiednich wierzchołków w danych struktura zwana stosem.

Krok 2)

Odwiedzisz element , który znajduje się na szczycie stosu, na przykład 1 i przejdź do jego sąsiednich węzłów. Dzieje się tak, ponieważ 0 zostało już odwiedzone. Dlatego odwiedzamy wierzchołek 2.

Krok 3)

Vertex 2 ma nieodwiedzony pobliski wierzchołek w 4. Dlatego dodajemy go do stosu i odwiedzamy go.

Krok 4)

Na koniec odwiedzimy ostatni wierzchołek 3 nie ma żadnych nieodwiedzonych węzłów sąsiadujących. Zakończyliśmy przemierzanie wykresu za pomocą algorytmu DFS.

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

BFS	DFS
BFS znajduje najkrótszą ścieżkę do miejsca docelowego.	DFS przechodzi na koniec poddrzewa, a następnie cofa się .
Pełna forma BFS to przeszukiwanie wszerz.	Pełna forma DFS to przeszukiwanie w głąb.
Używa kolejki do śledzenia następnej lokalizacji do odwiedzenia.	Używa stosu do śledzenia następnej lokalizacji do odwiedzenia.
BFS przechodzi zgodnie z poziomem drzewa.	DFS przechodzi zgodnie z głębokością drzewa.
Jest zaimplementowany przy użyciu FI Lista FO.	Jest zaimplementowany przy użyciu listy LIFO.
Wymaga większej ilości pamięci w porównaniu do DFS.	Wymaga mniej pamięci w porównaniu do BFS.
Ten algorytm zapewnia rozwiązanie z najmniejszą ścieżką.	Ten algorytm nie gwarantuje rozwiązania z najmniejszą ścieżką.
Nie ma potrzeby cofania w BFS.	Jest potrzeba cofania 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 rozwiązanie zostanie znalezione.	Jeśli nie znajdziesz żadnego celu, cofanie węzła liścia może pojawić się.

Zastosowania BFS

Oto aplikacje BFS:

Nieważone Wykresy:

Algorytm BFS może łatwo 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 peer to peer. Pozwoli to szybciej znaleźć wymagane dane.

Przeszukiwacze sieci:

Wyszukiwarki lub roboty sieciowe mogą z łatwością budować wiele poziomów indeksów przy użyciu 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.

Network Broadcasting:

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 wykresu DFS generuje najkrótsze drzewo ścieżki i minimalne drzewo opinają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.

Znajdowanie ścieżki:

Możemy specjalizować się w algorytmie DFS do przeszukiwania ścieżki między dwoma wierzchołkami.

Sortowanie topologiczne:

Jest używane 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.

Przeszukiwanie silnie połączonych składników wykresu:

Używana w grafie DFS, gdy istnieje ścieżka od każdego wierzchołka wykresu do pozostałych 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.