Zanim przyjrzymy się różnicom między BFS i DFS, najpierw powinniśmy wiedzieć o BFS i DFS osobno.
Co to jest BFS?
BFS oznacza Wyszukiwanie wszerz . Znany jest również jako przechodzenie przez poziom zamówienia . Struktura danych Queue jest używana do przeszukiwania wszerz. Kiedy używamy algorytmu BFS do poruszania się po grafie, możemy uznać dowolny węzeł za węzeł główny.
Rozważmy poniższy wykres przedstawiający przeszukiwanie wszerz.
Java mvc
Załóżmy, że uważamy węzeł 0 za węzeł główny. Zatem przejazd zostanie rozpoczęty od węzła 0.
Gdy węzeł 0 zostanie usunięty z kolejki, zostanie wydrukowany i oznaczony jako a odwiedzany węzeł.
Gdy węzeł 0 zostanie usunięty z kolejki, sąsiednie węzły węzła 0 zostaną wstawione do kolejki, jak pokazano poniżej:
Teraz węzeł 1 zostanie usunięty z kolejki; zostanie wydrukowany i oznaczony jako odwiedzony węzeł
Gdy węzeł 1 zostanie usunięty z kolejki, wszystkie sąsiadujące węzły węzła 1 zostaną dodane do kolejki. Sąsiednie węzły węzła 1 to 0, 3, 2, 6 i 5. Jednak do kolejki musimy wstawić tylko nieodwiedzone węzły. Ponieważ węzły 3, 2, 6 i 5 są nieodwiedzone; dlatego te węzły zostaną dodane do kolejki, jak pokazano poniżej:
Następny węzeł to 3 w kolejce. Zatem węzeł 3 zostanie usunięty z kolejki, zostanie wydrukowany i oznaczony jako odwiedzony, jak pokazano poniżej:
Gdy węzeł 3 zostanie usunięty z kolejki, wszystkie sąsiednie węzły węzła 3, z wyjątkiem węzłów odwiedzonych, zostaną dodane do kolejki. Sąsiednie węzły węzła 3 to 0, 1, 2 i 4. Ponieważ węzły 0, 1 są już odwiedzone, a węzeł 2 znajduje się w kolejce; dlatego musimy wstawić do kolejki tylko węzeł 4.
co to jest prolog
Teraz następnym węzłem w kolejce jest 2. Zatem 2 zostanie usunięte z kolejki. Zostanie wydrukowany i oznaczony jako odwiedzony, jak pokazano poniżej:
Gdy węzeł 2 zostanie usunięty z kolejki, wszystkie sąsiednie węzły węzła 2, z wyjątkiem węzłów odwiedzonych, zostaną dodane do kolejki. Sąsiednie węzły węzła 2 to 1, 3, 5, 6 i 4. Ponieważ węzły 1 i 3 zostały już odwiedzone, a węzły 4, 5, 6 są już dodane do kolejki; dlatego nie musimy wstawiać żadnego węzła do kolejki.
Następnym elementem jest 5. Zatem 5 zostanie usunięte z kolejki. Zostanie wydrukowany i oznaczony jako odwiedzony, jak pokazano poniżej:
Gdy węzeł 5 zostanie usunięty z kolejki, wszystkie sąsiednie węzły węzła 5, z wyjątkiem węzłów odwiedzonych, zostaną dodane do kolejki. Sąsiednie węzły węzła 5 to 1 i 2. Ponieważ oba węzły zostały już odwiedzone; w związku z tym nie ma wierzchołka do wstawienia do kolejki.
Następny węzeł to 6. Zatem 6 zostanie usunięte z kolejki. Zostanie wydrukowany i oznaczony jako odwiedzony, jak pokazano poniżej:
Gdy węzeł 6 zostanie usunięty z kolejki, wszystkie sąsiednie węzły węzła 6, z wyjątkiem węzłów odwiedzonych, zostaną dodane do kolejki. Sąsiadujące węzły węzła 6 to 1 i 4. Ponieważ węzeł 1 został już odwiedzony, a węzeł 4 jest już dodany do kolejki; dlatego w kolejce nie ma wierzchołka do wstawienia.
Następnym elementem w kolejce jest 4. Zatem 4 zostanie usunięte z kolejki. Zostanie wydrukowany i oznaczony jako odwiedzony.
Gdy węzeł 4 zostanie usunięty z kolejki, wszystkie sąsiednie węzły węzła 4, z wyjątkiem węzłów odwiedzonych, zostaną dodane do kolejki. Sąsiednie węzły węzła 4 to 3, 2 i 6. Ponieważ wszystkie sąsiednie węzły zostały już odwiedzone; dlatego w kolejce nie ma wierzchołka do wstawienia.
Co to jest DFS?
DFS oznacza pierwsze wyszukiwanie w głębi. W przechodzeniu DFS wykorzystywana jest struktura danych stosu, która działa na zasadzie LIFO (Last In First Out). W DFS przechodzenie można rozpocząć od dowolnego węzła lub można powiedzieć, że dowolny węzeł można uznać za węzeł główny, dopóki węzeł główny nie zostanie wymieniony w problemie.
Konwersja ciągu znaków na int w Javie
W przypadku BFS element usuwany z Kolejki, do Kolejki dodawane są sąsiednie węzły usuniętego węzła. Natomiast w DFS element usuwany ze stosu, wówczas do stosu dodawany jest tylko jeden sąsiedni węzeł usuniętego węzła.
Rozważmy poniższy wykres przedstawiający przeszukiwanie w głąb.
Rozważ węzeł 0 jako węzeł główny.
Najpierw wstawiamy element 0 na stos, jak pokazano poniżej:
Węzeł 0 ma dwa sąsiednie węzły, tj. 1 i 3. Teraz do przejścia możemy wziąć tylko jeden sąsiedni węzeł, 1 lub 3. Załóżmy, że rozważymy węzeł 1; dlatego 1 jest wstawiany na stos i drukowany, jak pokazano poniżej:
Teraz przyjrzymy się sąsiednim wierzchołkom węzła 1. Nieodwiedzone sąsiednie wierzchołki węzła 1 to 3, 2, 5 i 6. Możemy rozważyć dowolny z tych czterech wierzchołków. Załóżmy, że bierzemy węzeł 3 i wstawiamy go na stos, jak pokazano poniżej:
Linux edytuj plik
Rozważmy nieodwiedzone sąsiednie wierzchołki węzła 3. Nieodwiedzone sąsiednie wierzchołki węzła 3 to 2 i 4. Możemy wybrać dowolny z wierzchołków, tj. 2 lub 4. Załóżmy, że weźmiemy wierzchołek 2 i wstawimy go na stos, jak pokazano poniżej:
Nieodwiedzone sąsiednie wierzchołki węzła 2 to 5 i 4. Możemy wybrać dowolny z wierzchołków, tj. 5 lub 4. Załóżmy, że bierzemy wierzchołek 4 i wstawiamy go do stosu, jak pokazano poniżej:
Teraz rozważymy nieodwiedzone sąsiednie wierzchołki węzła 4. Nieodwiedzony sąsiedni wierzchołek węzła 4 to węzeł 6. Dlatego element 6 jest wstawiany do stosu, jak pokazano poniżej:
Po wstawieniu elementu 6 na stos przyjrzymy się nieodwiedzonym sąsiednim wierzchołkom węzła 6. Ponieważ nie ma nieodwiedzonych sąsiednich wierzchołków węzła 6, więc nie możemy wyjść poza węzeł 6. W tym przypadku wykonamy cofanie się . Najwyższy element, tj. 6, zostanie wyrzucony ze stosu, jak pokazano poniżej:
Najwyższym elementem stosu jest 4. Ponieważ z węzła 4 nie ma żadnych nieodwiedzonych sąsiednich wierzchołków; dlatego węzeł 4 zostaje wyrzucony ze stosu, jak pokazano poniżej:
Następnym najwyższym elementem stosu jest 2. Teraz przyjrzymy się nieodwiedzonym sąsiednim wierzchołkom węzła 2. Ponieważ pozostał tylko jeden nieodwiedzony węzeł, tj. 5, więc węzeł 5 zostanie wepchnięty na stos powyżej 2 i zostanie wydrukowany jak pokazano niżej:
wykres alokacji zasobów
Teraz sprawdzimy sąsiednie wierzchołki węzła 5, które nadal nie zostały odwiedzone. Ponieważ nie ma już żadnego wierzchołka do odwiedzenia, zdejmujemy element 5 ze stosu, jak pokazano poniżej:
Nie możemy przejść dalej o 5, więc musimy wykonać cofanie się. Podczas cofania najwyższy element zostanie wyrzucony ze stosu. Najwyższym elementem jest 5, który zostanie wyrzucony ze stosu i wracamy do węzła 2, jak pokazano poniżej:
Teraz sprawdzimy nieodwiedzone sąsiednie wierzchołki węzła 2. Ponieważ nie ma już żadnego sąsiedniego wierzchołka do odwiedzenia, wykonujemy cofanie się. W przypadku cofania najwyższy element, tj. 2, zostanie wyrzucony ze stosu i wracamy do węzła 3, jak pokazano poniżej:
Teraz sprawdzimy nieodwiedzone sąsiednie wierzchołki węzła 3. Ponieważ nie ma już żadnego sąsiedniego wierzchołka do odwiedzenia, wykonujemy cofanie się. W przypadku cofania najwyższy element, tj. 3, zostanie wyrzucony ze stosu i wracamy do węzła 1, jak pokazano poniżej:
Po wysunięciu elementu 3 sprawdzimy nieodwiedzone sąsiednie wierzchołki węzła 1. Ponieważ nie ma już żadnego wierzchołka do odwiedzenia; dlatego też zostanie wykonane cofanie. W przypadku cofania najwyższy element, tj. 1, zostanie wyrzucony ze stosu i wracamy do węzła 0, jak pokazano poniżej:
Sprawdzimy sąsiednie wierzchołki węzła 0, które nadal nie zostały odwiedzone. Ponieważ nie ma już żadnego sąsiedniego wierzchołka do odwiedzenia, wykonujemy cofanie się. W tym przypadku tylko jeden element, tj. 0 na stosie, zostanie wyrzucony ze stosu, jak pokazano poniżej:
Jak widać na powyższym rysunku, stos jest pusty. Musimy więc zatrzymać tutaj przechodzenie DFS, a drukowane elementy są wynikiem przechodzenia DFS.
Różnice pomiędzy BFS i DFS
Poniżej przedstawiono różnice między BFS i DFS:
| BFS | DFS | |
|---|---|---|
| Pełna forma | BFS oznacza wyszukiwanie wszerz. | DFS oznacza wyszukiwanie w głębi. |
| Technika | Jest to technika oparta na wierzchołkach, mająca na celu znalezienie najkrótszej ścieżki w grafie. | Jest to technika oparta na krawędziach, ponieważ najpierw badane są wierzchołki wzdłuż krawędzi, od węzła początkowego do końcowego. |
| Definicja | BFS to technika przechodzenia, w której najpierw eksplorowane są wszystkie węzły tego samego poziomu, a następnie przechodzimy do następnego poziomu. | DFS to także technika przechodzenia, w której przechodzenie rozpoczyna się od węzła głównego i eksploruje węzły tak daleko, jak to możliwe, aż dotrzemy do węzła, który nie ma nieodwiedzonych sąsiednich węzłów. |
| Struktura danych | Do przechodzenia przez BFS używana jest struktura danych kolejki. | Do przeglądania BFS używana jest struktura danych stosu. |
| Cofanie się | BFS nie stosuje koncepcji backtrackingu. | DFS wykorzystuje śledzenie wsteczne do przechodzenia przez wszystkie nieodwiedzone węzły. |
| Liczba krawędzi | BFS znajduje najkrótszą ścieżkę mającą minimalną liczbę krawędzi do przejścia od wierzchołka źródłowego do wierzchołka docelowego. | W DFS do przejścia z wierzchołka źródłowego do wierzchołka docelowego wymagana jest większa liczba krawędzi. |
| Optymalność | Przechodzenie BFS jest optymalne dla tych wierzchołków, które mają być przeszukiwane bliżej wierzchołka źródłowego. | Przechodzenie DFS jest optymalne dla tych grafów, w których rozwiązania są oddalone od wierzchołka źródłowego. |
| Prędkość | BFS jest wolniejszy niż DFS. | DFS jest szybszy niż BFS. |
| Przydatność drzewa decyzyjnego | Nie nadaje się do drzewa decyzyjnego, ponieważ wymaga najpierw zbadania wszystkich sąsiadujących węzłów. | Nadaje się do drzewa decyzyjnego. Na podstawie decyzji bada wszystkie ścieżki. Gdy cel zostanie znaleziony, zatrzymuje jego przemierzanie. |
| Pamięć wydajna | Nie jest wydajny pod względem pamięci, ponieważ wymaga więcej pamięci niż DFS. | Jest wydajny pod względem pamięci, ponieważ wymaga mniej pamięci niż BFS. |