Zarówno BFS, jak i DFS mają kluczowe znaczenie dla wyników wykresów. BFS to skrót od Breadth-First Search, a DFS to Depth-First Search. Oba z nich mają rozróżnienie między dwoma. Obaj używają nawet innej struktury danych do funkcjonowania, jedna używa struktury danych Queue, a druga to struktura danych Stack.
BFS vs DFS
Główna różnica między BFS i DFS polega na tym, że wyszukiwanie wszerz jest techniką opartą na wierzchołku, która pomaga wskazać najkrótszą ścieżkę na wykresie. Z drugiej strony, DFS lub Depth First Search to technika oparta na krawędzi. BFS to technika zależna od struktury danych kolejki. Z drugiej strony DFS zależy od struktury danych Stack.
BFS to technika stosowana do obliczania najkrótszej trasy na grafie przy użyciu struktury danych kolejki. Nadaje się do znajdowania wierzchołków w bliskich obszarach źródła. W przeciwieństwie do DFS, nie można go lepiej zastosować w drzewkach decyzyjnych, które można znaleźć w łamigłówkach lub grach.
DFS to technika stosowana do znajdowania najkrótszej ścieżki w grafie przy użyciu struktury danych Stack. Nadaje się do obszarów oddalonych od źródeł w rozwiązaniu. W przeciwieństwie do BFS może być lepiej zastosowany w podejmowaniu decyzji lub rozwiązywaniu problemów w grach.
Tabela porównawcza między BFS i DFS
| Parametry porównania | BFS | DFS |
| Pełna forma i definicja | BFS to skrót od Breadth-First Search. Jest to technika oparta na wierzchołku, która służy do znajdowania najkrótszej trasy na wykresie. | DFS to skrót od Depth First Search. Jest to technika oparta na krawędziach do znajdowania najkrótszej trasy na wykresie. |
| Zależność od struktury danych | Breadth-First Search lub BFS określa najkrótszą ścieżkę na wykresie za pomocą struktury danych kolejki. | Depth First Search lub DFS określa najkrótszą ścieżkę na wykresie za pomocą struktury danych Stack. |
| Zastosowania | W grafie nieważonym służy do znajdowania najkrótszej ścieżki pojedynczego źródła, ponieważ wykorzystuje najmniejszą liczbę krawędzi ze źródła wierzchołkowego. | W DFS, aby dotrzeć do punktu docelowego lub wierzchołka z dowolnego źródła, należy przejść przez więcej krawędzi. |
| Obszar przydatności | Jego obszar przydatności do wyszukiwania wierzchołków mieści się w bliskim zasięgu źródła. Nie nadaje się do tworzenia drzew decyzyjnych obecnych w grach. | Jego obszar przydatności mieści się w zakresie rozwiązań oddalonych od źródła. Jest bardziej odpowiedni do podejmowania decyzji lub rozwiązywania problemów w grach lub łamigłówkach. |
| Mechanizm | W tej technice podczas wizyty wybierany jest pojedynczy wierzchołek i zaznaczany, po czym sąsiednie są odwiedzane i umieszczane w kolejce. | Odwiedzone wierzchołki są umieszczane w stosie, a następnie w przypadku braku wierzchołków odwiedzane wierzchołki są usuwane. |
Co to jest BFS?
Za pomocą BFS wykres przesuwa się w chlebie w kierunku ruchu. Aby pamiętać o pobraniu następnego wierzchołka, w tej technice używana jest kolejka. Dzieje się tak, gdy w iteracji znajduje się w ślepym zaułku. Nie jest brane pod uwagę w przypadku drzew decyzyjnych, ponieważ w dużym stopniu obejmuje wszystkich sąsiadów. Jest stosunkowo powolny niż DFS. Algorytm BFS Złożoność czasowa BFS wynosi O(V+E) w czasie listy sąsiedztwa i O(V^2) w czasie macierzy sąsiedztwa. Tutaj E oznacza krawędzie, a V oznacza wierzchołki. Algorytm BFS w grafie może być używany w różnych dziedzinach.
BFS jest często używany do tworzenia każdego sąsiedniego węzła w połączeniach peer-to-peer. Indeks jest budowany za pomocą tej techniki przez roboty wyszukiwarek. Od stron źródłowych po nowe strony, pomaga znaleźć wszystkie powiązane linki. Jest to wymagane do odnalezienia sąsiednich miejsc za pomocą urządzenia do nawigacji GPS. Algorytm BFS jest używany podczas nadawania niektórych pakietów w sieci. Algorytm wyszukiwania ścieżek obejmuje BFS. Za pomocą tej techniki największy przepływ w sieci można znaleźć w algorytmie Forda-Fulkersona.
Co to jest DFS?
Z pomocą DFS, wykres jest przesuwany w głąb. Stos jest używany w tej technice, aby przypomnieć sobie o zdobyciu punktu obok poprzedniego. Wyszukiwanie odbywa się podczas wystąpienia dowolnej iteracji. W drzewie decyzyjnym należy wykonać dalszy trawers w celu rozszerzenia decyzji. Podsumowując, zwycięstwo zostało uznane. jest stosunkowo szybki niż BFS. Złożoność czasowa DFS wynosi O(V+E) podczas listy sąsiednich i O(V^2) podczas sąsiedniej macierzy. Tutaj E oznacza krawędzie, a V oznacza wierzchołki. DFS jest szeroko stosowany w różnych dziedzinach.
Gdy DFS jest wykonywane na wykresie nieważonym, dla każdej pary drzew o najkrótszej ścieżce opracowywane są minimalne drzewa opinające. Może być stosowany do identyfikacji cykli na wykresach. Jeśli w BFS zostanie znaleziona jedna tylna krawędź, to jest jeden cykl. Za pomocą tej techniki można znaleźć ścieżkę między u i v lub dwoma wierzchołkami. Algorytm DFS jest używany do sortowania topologicznego. Można go wykorzystać do określenia składowych, które są silnie powiązane na danym grafie. Komponenty są ukute tak, aby były silnie połączone, gdy istnieje ścieżka między każdym wierzchołkiem.
Główne różnice między BFS a DFS
Wniosek
Można więc stwierdzić, że BFS i DFS wyraźnie się od siebie różnią. BFS jest używany w grafie do znalezienia najkrótszej ścieżki za pomocą struktury danych kolejki, a DFS jest używany w grafie do znajdowania najkrótszej ścieżki za pomocą struktury danych stosu. BFS podczas swojej wizyty wybiera pojedynczy wierzchołek i zaznacza, po czym sąsiednie jest odwiedzane i zbierane w kolejce. Z drugiej strony, w DFS odwiedzone wierzchołki są uwzględniane w stosie iw przypadku braku wierzchołków wierzchołki są usuwane. Technika BFS opiera się na wierzchołku, a technika DFS na krawędzi.
