Różnica między BFS a DFS
Wyszukiwanie według szerokości (BFS) i Wyszukiwanie według głębokości (DFS) to dwa ważne algorytmy wykorzystywane do wyszukiwania. Wyszukiwanie szerokości pierwsze rozpoczyna wyszukiwanie od pierwszego węzła, a następnie przechodzi przez poziomy bliższe węzła głównego, podczas gdy algorytm wyszukiwania głębokiego pierwszego rozpoczyna się od pierwszego węzła, a następnie kończy ścieżkę do końcowego węzła odpowiedniej ścieżki. Oba algorytmy przechodzą przez każdy węzeł podczas wyszukiwania. Dla obu algorytmów zapisywane są różne kody, aby wykonać proces przejścia. Są one również uważane za ważne algorytmy wyszukiwania w sztucznej inteligencji.
W tym temacie poznamy BFS VS DFS.
Jak działają BFS i DFS?
Mechanizm działania obu algorytmów wyjaśniono poniżej przykładami. Proszę zapoznać się z nimi, aby lepiej zrozumieć zastosowane podejście.
Przykład pierwszego wyszukiwania szerokości
- Krok 1: N1 jest węzłem głównym, więc zacznie się tutaj. N1 jest połączony z trzema węzłami N2, N3 i N4. Wszystkie trzy węzły nie są jeszcze odwiedzane. Zaczynamy od N2 i przechowujemy go w kolejce. Zatem kolejka o nazwie Q zawiera tylko N2.
P: N2
- Krok 2: Następnie węzłem, który jest podłączony do N1, jest N3. Ponieważ przeszliśmy przez węzeł lub odwiedziliśmy go, będziemy go przechowywać w kolejce. Zaktualizowana kolejka to
P: N3, N2
- Krok 3: Następnie węzłem, który jest podłączony do węzła głównego, jest N4. Będziemy przechowywać go w kolejce.
P: N4, N3, N2
- Krok 4: Wszystkie węzły podłączone do N1 są przechowywane w kolejce. Teraz usuwamy N2 z kolejki zgodnie z zasadą First in First Out (FIFO) i znajdujemy węzły podłączone do N2, tj. N5. N5 nie jest odwiedzany raz, więc będziemy przechowywać go w kolejce.
P: N5, N4, N3
- Krok 5: Wszystkie wierzchołki są odwiedzane, więc kontynuujemy usuwanie węzłów z kolejki, aż będzie pusta.
Przykład pierwszego wyszukiwania głębokości
- Krok 1: Zaczniemy od N1 jako węzła początkowego i zapiszemy go na stosie S. N1 jest połączony z trzema sąsiadującymi węzłami N2, N3 i N4. Począwszy od N2 (możesz zacząć alfabetycznie lub numerycznie), umieścimy to na stosie.
S: N2 (góra), N1
- Krok 2: Teraz sąsiednimi węzłami N2 są N1 i N5. Ponieważ N1 jest już obecny na stosie, co oznacza, że jest odwiedzany, więc weźmiemy N5 i umieścimy go na stosie S.
S: N5 (góra), N2, N1
- Krok 3: Teraz sąsiednimi węzłami N5 są N3 i N4. Zaczynamy od N3 i umieszczamy go na stosie.
S: N3 (góra), N5, N2, N1
Teraz N3 jest podłączony do N5 i N1, które są już obecne na stosie, co oznacza, że są odwiedzane, więc usuniemy N3 ze stosu zgodnie z zasadą Last in First Out (LIFO).
S: N5 (góra), N2, N1
- Krok 4: Teraz umieścimy ostatni węzeł, którego nie napotkaliśmy podczas całej podróży w N4 i umieścimy go na stosie.
S: N4 (góra), N5, N2, N1
- Krok 5: Teraz nie jesteśmy pominięci w żadnych innych węzłach, więc sprawdzimy stos, jeśli są jakieś węzły podłączone do odpowiednich węzłów, które nie są odwiedzane. Jeśli wszystkie połączone węzły zostaną odwiedzone, usuniemy węzły obecne na stosie. Na przykład N4 nie ma węzłów łączących, których nie sprawdziliśmy, więc usuniemy go ze stosu. Podobnie możemy sprawdzić inne węzły. Algorytm zatrzymuje się, gdy stos jest pusty.
Bezpośrednie porównanie między BFS VS DFS (infografiki)
Poniżej znajduje się 6 najważniejszych różnic między BFS VS DFS
Kluczowe różnice między BFS i DFS
Omówmy niektóre z głównych kluczowych różnic między BFS a DFS
- Wyszukiwanie szerokości (BFS) rozpoczyna się od węzła głównego i odwiedza wszystkie odpowiednie dołączone do niego węzły, podczas gdy DFS rozpoczyna się od węzła głównego i kończy pełną ścieżkę dołączoną do węzła.
- BFS podąża za kolejką, podczas gdy DFS podąża za stosem.
- Podejście stosowane w BFS jest optymalne, podczas gdy proces stosowany w DFS nie jest optymalny.
- Jeśli naszym celem jest znalezienie najkrótszej ścieżki, preferowany jest BFS niż DFS.
Tabela porównawcza BFS i DFS
Omówmy najlepsze porównanie między BFS a DFS
| BFS | DFS |
| Pełna forma BFS to Wyszukiwanie na szerokość. | Pełna forma DFS to Głębokie wyszukiwanie |
| BFS ma znaleźć najkrótszą odległość i zaczyna się od pierwszego lub głównego węzła i przesuwa się po wszystkich swoich węzłach dołączonych do odpowiednich węzłów. Po przejściu do poniższego przykładu możesz uzyskać wyraźny widok jego mechanizmu roboczego. | DFS stosuje podejście oparte na głębokości i uzupełnia pełną ścieżkę przez wszystkie węzły dołączone do odpowiedniego węzła. Po przejściu do poniższego przykładu możesz uzyskać wyraźny widok jego mechanizmu roboczego. |
| Odbywa się to przy użyciu zasady kolejki, która jest metodą FIFO (First In First Out). | Odbywa się to przy użyciu zasady Stack, która jest metodą Last In First Out (LIFO). |
| Węzły, które są przemierzane więcej niż jeden raz, są usuwane z kolejki. | Węzły, które są odwiedzane, są wstawiane do stosu, a później, jeśli nie ma więcej węzłów do odwiedzenia, są one usuwane. |
| Jest względnie wolniejszy niż Głębokie pierwsze wyszukiwanie. | Jest szybszy niż algorytm pełnego wyszukiwania. |
| Alokacja pamięci jest większa niż algorytm Głębokie Pierwsze Wyszukiwanie. | Alokacja pamięci jest stosunkowo mniejsza niż w przypadku pierwszego algorytmu wyszukiwania |
Wniosek
Istnieje wiele aplikacji, w których powyższe algorytmy są używane jako uczenie maszynowe lub w celu znalezienia rozwiązań związanych ze sztuczną inteligencją itp. Są one używane głównie na wykresach w celu ustalenia, czy jest to dwustronna, czy nie, w celu wykrycia połączonych cykli lub komponentów. Są również uważane za ważne algorytmy w znalezieniu ścieżki lub znalezieniu najkrótszej odległości. W zależności od wymagań firmy możemy zastosować dwa algorytmy. Jednak pierwsze wyszukiwanie jest uważane za optymalny sposób, a nie algorytm głębokiego wyszukiwania.
Polecane artykuły
To jest przewodnik po BFS VS DFS. Tutaj omawiamy różnice klucza BFS VS DFS z infografiką i tabelą porównawczą. Możesz także zapoznać się z następującymi artykułami, aby dowiedzieć się więcej -
- Algorytm BFS
- TeraData vs Oracle
- Big Data a hurtownia danych
- Big Data vs Apache Hadoop: porównanie 4 najlepszych wyników