Różnica między BFS i DFS

BFS vs DFS

Szerokość pierwszego wyszukiwania (znana również jako BFS) to metoda wyszukiwania używana do poszerzenia wszystkich węzłów danego wykresu. Wykonuje to zadanie, przeszukując każde pojedyncze rozwiązanie w celu zbadania i rozwinięcia tych węzłów (lub kombinacji w nich sekwencji). W związku z tym BFS nie używa algorytmu heurystycznego (lub algorytmu, który szuka rozwiązania w wielu scenariuszach). Po uzyskaniu wszystkich węzłów są one dodawane do kolejki znanej jako kolejka Pierwsze wejście, Pierwsze wyjście. Te węzły, które nie zostały zbadane, są „przechowywane” w kontenerze oznaczonym jako „otwarte”; po zbadaniu są transportowane do kontenera oznaczonego jako „zamknięty”.

Głębokie pierwsze wyszukiwanie (znane również jako DFS) to metoda wyszukiwania, która wnika głębiej w węzeł podrzędny wyszukiwania, dopóki nie zostanie osiągnięty cel (lub dopóki nie będzie węzła bez innych permutacji lub „dzieci”). Po znalezieniu jednego celu wyszukiwanie powoduje powrót do poprzedniego węzła, który poszedł z rozwiązaniem, powtarzając ten proces do momentu pomyślnego przeszukania wszystkich węzłów. W związku z tym węzły są nadal odkładane na dalszą eksplorację - nazywa się to implementacją nierekurencyjną.

Cechy BFS to złożoność przestrzeni i czasu, kompletność, dowód kompletności i optymalność. Złożoność przestrzeni odnosi się do proporcji liczby węzłów na najgłębszym poziomie wyszukiwania. Złożoność czasu odnosi się do faktycznej ilości „czasu” wykorzystanego do rozważenia każdej ścieżki, którą węzeł zajmie podczas wyszukiwania. Kompletność jest w zasadzie wyszukiwaniem, które znajduje rozwiązanie na wykresie niezależnie od tego, jaki to rodzaj wykresu. Dowodem kompletności jest najniższy poziom, na którym cel znajduje się w węźle na określonej głębokości. Wreszcie, optymalność odnosi się do BFS, który nie jest ważony - jest to wykres stosowany dla kosztu jednostkowego.

DFS jest najbardziej naturalnym wyjściem przy użyciu drzewa opinającego - które jest drzewem złożonym ze wszystkich wierzchołków i niektórych krawędzi na niekierowanym grafie. W tej formacji wykres jest podzielony na trzy klasy: Krawędzie do przodu, wskazujące od węzła do węzła potomnego; tylne krawędzie, wskazujące od węzła do wcześniejszego węzła; i poprzeczne krawędzie, które nie powodują żadnego z nich.

Streszczenie:

1. BFS przeszukuje każde rozwiązanie na wykresie w celu rozszerzenia swoich węzłów; DFS zagłębia się głęboko w węźle potomnym, aż do osiągnięcia celu.

2. Cechy BFS to złożoność przestrzeni i czasu, kompletność, dowód kompletności i optymalność; najbardziej naturalnym wyjściem dla DFS jest drzewo opinające z trzema klasami: przednimi, tylnymi i poprzecznymi.