Różnica między BFS i DFS

• 2019

Główną różnicą między BFS i DFS jest to, że BFS postępuje poziom po poziomie, podczas gdy DFS następuje po pierwszej ścieżce od początku do węzła końcowego (vertex), następnie od innej ścieżki od początku do końca, i tak dalej, aż wszystkie odwiedzone węzły zostaną odwiedzone. Ponadto system BFS używa kolejki do przechowywania węzłów, podczas gdy system plików DFS używa stosu do przechodzenia między węzłami.

BFS i DFS są metodami przeszukiwania używanymi podczas przeszukiwania wykresu. Przebieg wykresu to proces odwiedzania wszystkich węzłów wykresu. Wykres to grupa Vertices "V" i krawędzie "E" łączące się z wierzchołkami.

Wykres porównania

Podstawa do porównania	BFS	DFS
Podstawowy	Algorytm oparty na wierzchołku	Algorytm oparty na krawędziach
Struktura danych używana do przechowywania węzłów	Kolejka	Stos
Zużycie pamięci	Nieskuteczny	Wydajny
Struktura zbudowanego drzewa	Szeroki i krótki	Wąskie i długie
Przemierzaj modę	Najstarsze nieodwiedzone wierzchołki są badane na początku.	Wierzchołki wzdłuż krawędzi są badane na samym początku.
Optymalność	Optymalny do znalezienia najkrótszej odległości, nie kosztem.	Nie optymalny
Podanie	Analizuje wykres dwudzielny, podłączony komponent i najkrótszą ścieżkę obecną na wykresie.	Analizuje wykres połączony z dwiema krawędziami, silnie połączony wykres, wykres acykliczny i kolejność topologiczną.

Definicja BFS

Szerokość pierwszego przeszukiwania (BFS) jest metodą przechodzenia używaną na wykresach. Używa kolejki do przechowywania odwiedzonych wierzchołków. W tej metodzie nacisk kładziony jest na wierzchołki wykresu, najpierw wybierany jest jeden wierzchołek, a następnie odwiedzany i oznaczany. Wierzchołki sąsiadujące z odwiedzanym wierzchołkiem są następnie odwiedzane i przechowywane w kolejce kolejno. Podobnie zapisane wierzchołki są następnie traktowane jeden po drugim, a ich sąsiednie wierzchołki są odwiedzane. Węzeł jest w pełni eksplorowany przed odwiedzeniem dowolnego innego węzła na wykresie, innymi słowy, najpierw przechodzi przez płytkie nieodkryte węzły.

Przykład

Mamy wykres, którego wierzchołki to A, B, C, D, E, F, G. Rozważając A jako punkt wyjścia. Kroki związane z procesem są następujące:

• Wierzchołek A jest rozszerzany i przechowywany w kolejce.
• Wierzchołki B, D i G z A są rozszerzane i przechowywane w kolejce w międzyczasie usunięty wierzchołek A.
• Teraz B na przednim końcu kolejki jest usuwany wraz z zachowaniem jego następnych wierzchołków E i F.
• Wierzchołek D na przedniej części kolejki został usunięty, a jego połączony węzeł F jest już odwiedzony.
• Wierzchołek G jest usuwany z kolejki i ma następcę E, które jest już odwiedzone.
• Teraz E i F są usuwane z kolejki, a jej następny wierzchołek C jest przesuwany i przechowywany w kolejce.
• W końcu C jest również usuwany, a kolejka jest pusta, co oznacza, że ​​jesteśmy skończeni.
• Wygenerowane wyjście to - A, B, D, G, E, F, C.

Aplikacje-

System BFS może być przydatny w wyszukiwaniu, czy wykres zawiera komponenty, czy nie. Można go również wykorzystać do wykrywania wykresu dwudzielnego .

Wykres jest dwuczęściowy, gdy wierzchołki wykresu są podzielone na dwa rozłączne zbiory; żadne dwa sąsiednie wierzchołki nie znajdowałyby się w tym samym zestawie. Inną metodą sprawdzania wykresu dwuczęściowego jest sprawdzenie wystąpienia nieparzystego cyklu na wykresie. Dwustronny wykres nie może zawierać cyklu nieparzystego.

BFS jest również lepszy w znalezieniu najkrótszej ścieżki na wykresie może być postrzegany jako sieć.

Definicja systemu plików DFS

Głębokość Metoda przeszukiwania pierwszego wyszukiwania (DFS) używa stosu do przechowywania odwiedzonych wierzchołków. DFS jest metodą opartą na krawędzi i działa w sposób rekurencyjny, w którym wierzchołki są eksplorowane wzdłuż ścieżki (krawędzi). Eksploracja węzła zostaje zawieszona, gdy tylko zostanie znaleziony kolejny nieodkryty węzeł, a najgłębsze, nieodkryte węzły będą się przemieszczać. DFS przemierzyć / odwiedzić każdy wierzchołek dokładnie jeden raz i każda krawędź jest dokładnie sprawdzana dwa razy.

Przykład

Podobne do BFS pozwala na wykonanie tego samego wykresu dla wykonywania operacji DFS, a zaangażowane kroki to:

• Rozważenie A jako początkowego wierzchołka, który jest eksplorowany i przechowywany w stosie.
• B następny wierzchołek A jest przechowywany w stosie.
• Wierzchołek B ma dwóch następców E i F, a wśród nich alfabetycznie E jest eksplorowany jako pierwszy i zapisywany w stosie.
• Następca wierzchołka E, tj. G, jest przechowywany w stosie.
• Wierzchołek G ma dwa połączone wierzchołki i oba są już odwiedzone, więc G jest wyskakiwane ze stosu.
• Podobnie E zostały również usunięte.
• Teraz wierzchołek B znajduje się na szczycie stosu, jego inny węzeł (wierzchołek) F jest eksplorowany i przechowywany w stosie.
• Vertex F ma dwa następniki C i D, pomiędzy nimi C jest najpierw przesuwany i przechowywany w stosie.
• Wierzchołek C ma tylko jeden poprzednik, który jest już odwiedzony, więc jest usuwany ze stosu.
• Teraz wierzchołek D podłączony do F jest odwiedzany i przechowywany w stosie.
• Ponieważ wierzchołek D nie ma żadnych nieodwiedzonych węzłów, dlatego D jest usuwany.
• Podobnie, F, B i A również są pęknięte.
• Wygenerowane wyjście to - A, B, E, G, F, C, D.

Podanie-

Aplikacje systemu plików DFS obejmują przegląd wykresu połączonego z dwoma krawędziami, silnie połączonego wykresu, wykresu acyklicznego i porządku topologicznego .

Wykres nazywa się dwiema krawędziami połączonymi wtedy i tylko wtedy, gdy pozostaje połączone, nawet jeśli jedna z jego krawędzi zostanie usunięta. Ta aplikacja jest bardzo przydatna w sieciach komputerowych, gdzie awaria jednego łącza w sieci nie wpłynie na pozostałą sieć i nadal będzie połączona.

Silnie połączony wykres to wykres, w którym musi istnieć ścieżka między zamówionymi parami wierzchołków. DFS jest używany w ukierunkowanym grafie do wyszukiwania ścieżki między każdą uporządkowaną parą wierzchołków. DFS może łatwo rozwiązać problemy z łącznością.

Kluczowe różnice między BFS i DFS

1. BFS jest algorytmem opartym na wierzchołkach, podczas gdy DFS jest algorytmem brzegowym.
2. Struktura danych kolejek jest używana w systemie BFS. Z drugiej strony system plików DFS używa stosu lub rekursji.
3. Pamięć jest wydajnie wykorzystywana w DFS, a wykorzystanie przestrzeni w systemie BFS nie jest efektywne.
4. BFS jest optymalnym algorytmem, a DFS nie jest optymalny.
5. DFS tworzy wąskie i długie drzewa. W przeciwieństwie do tego, BFS konstruuje szerokie i krótkie drzewa.

Wniosek

BFS i DFS, obie techniki wyszukiwania wykresów mają podobny czas działania, ale inne zużycie przestrzeni, DFS zajmuje przestrzeń liniową, ponieważ musimy zapamiętać pojedynczą ścieżkę z nieodkrytymi węzłami, podczas gdy BFS utrzymuje każdy węzeł w pamięci.

DFS dostarcza głębszych rozwiązań i nie jest optymalny, ale działa dobrze, gdy rozwiązanie jest gęste, podczas gdy BFS jest optymalny, który na początku wyszukuje optymalny cel.