główna różnica między BFS i DFS polega na tym, że BFS przechodzi z poziomu na poziom, podczas gdy DFS podąża najpierw ścieżką od początku do końca węzła (wierzchołek), następnie inną ścieżką od początku do końca i tak dalej, aż wszystkie węzły zostaną odwiedzone. Ponadto BFS używa kolejki do przechowywania węzłów, podczas gdy DFS używa stosu do przechodzenia węzłów.
BFS i DFS są metodami przeszukiwania wykresu. Graph traversal to proces odwiedzania wszystkich węzłów grafu. Graf to grupa wierzchołków ” V „i krawędzi” E ” łączących się z wierzchołkami.
treść: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure z zbudowanego drzewa | szerokie i krótkie | wąskie i długie |
| przemierzające modę | najstarsze niezwiedzone wierzchołki są badane na początku. | wierzchołki wzdłuż krawędzi są badane na początku. |
| optymalność | optymalna dla znalezienia najkrótszej odległości, Nie w kosztach. | Nie optymalny |
| aplikacja | bada Wykres dwudzielny, połączony składnik i najkrótszą ścieżkę obecną w grafie. | analizuje Graf połączony dwoma krawędziami, Graf silnie połączony, Graf acykliczny i porządek topologiczny. |
definicja BFS
Szerokość pierwszego wyszukiwania (BFS) jest metodą przeszukiwania używaną w wykresach. Używa kolejki do przechowywania odwiedzonych wierzchołków. W tej metodzie podkreślenie znajduje się na wierzchołkach grafu, najpierw zaznacza się jeden wierzchołek, następnie jest odwiedzany i oznaczany. Wierzchołki sąsiadujące z odwiedzanym wierzchołkiem są następnie odwiedzane i zapisywane kolejno w kolejce.
podobnie przechowywane wierzchołki są następnie traktowane jeden po drugim, a ich sąsiednie wierzchołki są odwiedzane. Węzeł jest w pełni zbadany przed odwiedzeniem jakiegokolwiek innego węzła na wykresie, innymi słowy, najpierw przemierza płytsze niezbadane węzły.
przykład
mamy wykres, którego wierzchołkami są A, B, C, D, E, F, G. biorąc pod uwagę a jako punkt początkowy. Kroki związane z procesem to:
- wierzchołek a jest rozwijany i zapisywany w kolejce.
- wierzchołki B, D i G następców A są rozwijane i przechowywane w kolejce, a wierzchołek a usuwany.
- teraz B na przednim końcu kolejki jest usuwany wraz z przechowywaniem kolejnych wierzchołków E i F.
- wierzchołek D znajdujący się na przednim końcu kolejki jest usuwany, a jego połączony węzeł F jest już odwiedzany.
- wierzchołek G jest usuwany z kolejki i ma następcę E, który jest już odwiedzany.
- teraz E I F są usuwane z kolejki, a jej następca wierzchołek C jest przemierzany i przechowywany w kolejce.
- w końcu C jest również usuwane, a kolejka jest pusta, co oznacza, że skończyliśmy.
- wygenerowane Wyjście To-A, B, D, G, E, F, C.
Aplikacje
BFS może być przydatny w sprawdzaniu, czy Wykres ma połączone komponenty, czy nie. A także może być stosowany w wykrywaniu wykresu dwuczęściowego.
Graf jest dwudzielny, gdy wierzchołki grafu są rozdzielone na dwa rozłączne zbiory; żadne dwa sąsiadujące wierzchołki nie mogłyby znajdować się w tym samym zbiorze. Inną metodą sprawdzania dwuczęściowego grafu jest sprawdzenie występowania nieparzystego cyklu na grafie. Wykres dwudzielny nie może zawierać nieparzystego cyklu.
BFS jest również lepszy w znajdowaniu najkrótszej ścieżki na wykresie.
definicja DFS
metoda traversing Depth First Search (DFS) wykorzystuje stos 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ą badane wzdłuż ścieżki (krawędzi). Eksploracja węzła zostaje zawieszona, gdy tylko znajdzie się inny niezbadany węzeł, a najgłębsze niezbadane węzły są przemierzane przede wszystkim. DFS przemierza / odwiedza każdy wierzchołek dokładnie raz, a każda krawędź jest sprawdzana dokładnie dwa razy.
przykład
podobny do BFS pozwala na wykonanie tego samego wykresu dla operacji DFS, a zaangażowane kroki to:
- rozważając a jako początkowy wierzchołek, który jest badany i przechowywany w stosie.
- w stosie przechowywany jest wierzchołek a.
- wierzchołek B ma dwa następniki E I F, wśród nich Alfabetycznie E jest badany jako pierwszy i przechowywany w stosie.
- następca wierzchołka e, czyli G jest przechowywany w stosie.
- wierzchołki G mają dwa połączone wierzchołki i oba są już odwiedzone, więc G jest wyskakiwane ze stosu.
- podobnie, E S również usunięte.
- teraz wierzchołek B znajduje się na szczycie stosu, jego kolejny węzeł(wierzchołek) F jest badany i przechowywany w stosie.
- wierzchołek F ma dwa następniki C I D, między nimi C jest najpierw przemierzane i przechowywane w stosie.
- wierzchołek C ma tylko jeden poprzednik, który jest już odwiedzony, więc jest usuwany ze stosu.
- teraz wierzchołek d połączony z F jest odwiedzany i przechowywany w stosie.
- ponieważ wierzchołek D nie ma żadnych niezwieszonych węzłów, dlatego D jest usuwany.
- podobnie, F, B I A są również wyświetlane.
- wygenerowane Wyjście To-A, B, E, G, F, C, D.
zastosowanie
zastosowania DFS obejmują kontrolę dwóch połączonych krawędzi grafu, silnie połączonego grafu, grafu acyklicznego i porządku topologicznego.
grafem nazywa się dwie krawędzie połączone wtedy i tylko wtedy, gdy pozostaje połączony, 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 podłączony.
Graf silnie połączony to Graf, w którym musi istnieć ścieżka pomiędzy uporządkowanymi parami wierzchołków. DFS jest używany w grafie skierowanym do przeszukiwania ścieżki pomiędzy każdą uporządkowaną parą wierzchołków. System DFS może łatwo rozwiązać problemy z łącznością.
kluczowe różnice między BFS i DFS
- BFS jest algorytmem opartym na wierzchołkach, podczas gdy DFS jest algorytmem opartym na krawędzi.
- Struktura danych kolejki jest używana w BFS. Z drugiej strony, DFS używa stosu lub rekurencji.
- przestrzeń pamięci jest efektywnie wykorzystywana w DFS, podczas gdy wykorzystanie przestrzeni w BFS nie jest efektywne.
- BFS jest optymalnym algorytmem, podczas gdy DFS nie jest optymalny.
- DFS buduje wąskie i długie drzewa. Podobnie jak przeciw, BFS konstruuje szerokie i krótkie drzewo.
podsumowanie
BFS i DFS, obie techniki wyszukiwania wykresów mają podobny czas działania, ale inne zużycie przestrzeni, DFS zajmuje przestrzeń liniową, ponieważ musimy pamiętać o pojedynczej ścieżce z niezbadanymi węzłami, podczas gdy BFS przechowuje każdy węzeł w pamięci.
DFS daje głębsze rozwiązania i nie jest optymalny, ale działa dobrze, gdy rozwiązanie jest gęste, podczas gdy BFS jest optymalny, który najpierw szuka optymalnego celu.