DFS — algorytm przeszukiwania w głąb wyjaśniony

Przeszukiwanie w głąb, czyli DFS, to algorytm służący do eksplorowania drzewa lub grafu przez podążanie jedną ścieżką tak daleko, jak to możliwe, zanim nastąpi cofanie. Mówiąc prościej: DFS schodzi coraz głębiej, aż utknie, a potem wraca do ostatniego miejsca, w którym była jeszcze dostępna inna gałąź.

Jeśli masz zapamiętać jedną rzecz, niech będzie to ta: DFS oznacza „idź w głąb, potem się cofnij”.

Co robi przeszukiwanie w głąb

DFS można stosować zarówno do drzew, jak i do ogólnych grafów. Zaczynając od jednego wierzchołka, algorytm wielokrotnie przechodzi do nieodwiedzonego sąsiada. Gdy dotrze do wierzchołka, który nie ma już żadnego nieodwiedzonego sąsiada, cofa się do poprzedniego wierzchołka i kontynuuje stamtąd.

To cofanie jest cechą definiującą DFS. W implementacjach rekurencyjnych stos wywołań obsługuje je automatycznie. W implementacjach iteracyjnych tę samą rolę pełni jawny stos.

Dlaczego kolejność DFS może się zmieniać

DFS nie daje jednej uniwersalnej kolejności odwiedzania. Dokładna kolejność zależy od tego, w jakiej kolejności rozpatrywani są sąsiedzi.

Na przykład, jeśli wierzchołek ma sąsiadów $B$ i $C$, odwiedzenie najpierw $B$ może dać inną kolejność DFS niż odwiedzenie najpierw $C$. W obu przypadkach nadal jest to DFS, ponieważ reguła pozostaje taka sama: schodź jak najgłębiej, zanim zaczniesz badać sąsiednią gałąź.

Przykład DFS na małym grafie

Załóżmy, że graf ma następujące połączenia:

• $A$ jest połączone z $B$ i $C$
• $B$ jest połączone z $D$ i $E$
• $C$ jest połączone z $F$

Załóżmy, że zawsze sprawdzamy sąsiadów od lewej do prawej i zaczynamy w $A$.

DFS przebiega wtedy tak:

1. Odwiedź $A$
2. Przejdź do $B$
3. Przejdź do $D$
4. $D$ nie ma nieodwiedzonego sąsiada, więc cofnij się do $B$
5. Z $B$ przejdź do $E$
6. $E$ jest już zakończone, więc cofnij się do $B$, a potem do $A$
7. Z $A$ przejdź do $C$
8. Z $C$ przejdź do $F$

Zatem jedna poprawna kolejność odwiedzania w DFS to:

$$A, B, D, E, C, F$$

Kluczowa idea jest taka, że DFS kończy stronę $A \to B$, zanim zacznie stronę $A \to C$. Jeśli zmienisz kolejność sąsiadów, kolejność odwiedzania też może się zmienić.

Dlaczego cofanie używa stosu

DFS zawsze potrzebuje sposobu, by pamiętać, dokąd wrócić po dojściu do ślepego końca. Dlatego stosy naturalnie pojawiają się w DFS.

W rekurencyjnym DFS każde wywołanie funkcji czeka, gdy przeszukiwanie schodzi głębiej, a program wraca w odwrotnej kolejności podczas cofania. W iteracyjnym DFS odkładasz wierzchołki na stos i zdejmujesz je z niego, gdy przychodzi czas, by kontynuować od ostatniego niedokończonego punktu.

Złożoność czasowa i pamięciowa DFS

Jeśli graf jest zapisany jako lista sąsiedztwa, a każdy wierzchołek jest oznaczany przy pierwszej wizycie, to DFS działa w czasie

$$O(V + E)$$

dla osiągalnej części grafu, gdzie $V$ to liczba wierzchołków, a $E$ to liczba krawędzi.

Dodatkowa pamięć to zwykle

$$O(V)$$

ponieważ struktura odwiedzonych oraz stos rekurencji lub jawny stos mogą rosnąć wraz z liczbą wierzchołków.

Typowe błędy w DFS

Zapominanie o oznaczaniu odwiedzonych wierzchołków

W ogólnym grafie pominięcie sprawdzania odwiedzenia może sprawić, że DFS będzie krążył po cyklu bez końca. Nawet w drzewie zapisanym jako graf nieskierowany nadal trzeba unikać natychmiastowego powrotu do rodzica, chyba że kod jawnie obsługuje ten przypadek.

Zakładanie, że DFS znajduje najkrótszą ścieżkę

DFS może znaleźć jakąś ścieżkę, ale na ogół nie gwarantuje najkrótszej ścieżki w grafie nieważonym. Jeśli celem jest najkrótsza ścieżka i wszystkie krawędzie mają tę samą wagę, BFS jest zwykle lepszym punktem wyjścia.

Traktowanie kolejności DFS jako jedynej możliwej

Kolejność zależy od kolejności sąsiadów. Jeśli ta kolejność się zmieni, kolejność przechodzenia również może się zmienić.

Kiedy używa się przeszukiwania w głąb

DFS jest przydatny, gdy chcesz badać strukturę, a nie tylko najbliższą odległość w pierwszej kolejności. Typowe zastosowania obejmują:

• sprawdzanie, czy do danego wierzchołka da się dotrzeć
• znajdowanie spójnych składowych
• wykrywanie cykli w niektórych ustawieniach grafowych
• przechodzenie po drzewach
• rozwiązywanie problemów z cofaniem, takich jak labirynty lub przeszukiwanie łamigłówek

Główny powód, dla którego pojawia się tak często, jest prosty: „idź w głąb, potem się cofnij” pasuje do wielu rekurencyjnych struktur problemów.

DFS a BFS: praktyczna różnica

DFS najpierw schodzi jedną gałęzią. BFS bada wszystkie wierzchołki w danej odległości, zanim przejdzie do następnej odległości.

Jeśli zależy ci na pełnej eksploracji albo na strukturze rekurencyjnej, DFS jest często naturalnym wyborem. Jeśli zależy ci na najkrótszej ścieżce w grafie nieważonym, BFS jest często bezpieczniejszym pierwszym wyborem.

Spróbuj podobnego przejścia

Narysuj mały graf z sześcioma wierzchołkami i wybierz stałą kolejność sąsiadów. Przeprowadź DFS ręcznie i zapisz dokładnie, kiedy idziesz naprzód, a kiedy się cofasz. Jeśli po zmianie kolejności sąsiadów zmieni się też kolejność przejścia, to nie jest błąd. To część działania DFS.