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: