Przeszukiwanie w głąb (DFS)
Wejdź do labiryntu, idź, aż trafisz na ślepy zaułek, potem cofnij się do ostatniego rozwidlenia i spróbuj następnej drogi. Tak samo przeszukiwanie w głąb bada graf. To jeden z najprostszych algorytmów grafowych, a stos, który prowadzi, mówi więcej, niż można by się spodziewać.
Idea
Graf to zbiór wierzchołków połączonych krawędziami: pokoje i drzwi, strony internetowe i linki, zadania i zadania, od których zależą. Przeszukiwanie w głąb odwiedza każdy wierzchołek osiągalny ze startu, ale w określonej kolejności: zawsze idzie dalej od wierzchołka, do którego dotarło najpóźniej. Prowadzi stos wierzchołków, w których się znajduje. Nowy wierzchołek trafia na szczyt, a wierzchołek schodzi ze stosu dopiero wtedy, gdy wszystko wokół niego zostało zbadane.
Krok po kroku
Połóż start na stosie i nadaj mu numer odwiedzin 1. Spójrz na kolejnego sąsiada wierzchołka na szczycie. Jeśli nie był jeszcze widziany, nadaj mu następny numer odwiedzin, zapamiętaj wierzchołek, z którego do niego dotarto, i połóż go na szczycie stosu. Jeśli był już widziany, pomiń go. Gdy wierzchołek na szczycie nie ma już sąsiadów do sprawdzenia, jest przetworzony: zdejmij go i kontynuuj od wierzchołka pod nim. Zakończ, gdy stos jest pusty albo gdy osiągniesz cel.
Przykład
Weź graf z krawędziami A–B, A–C, B–D, C–D, C–E i D–F, zacznij od A i sprawdzaj sąsiadów w kolejności alfabetycznej. Z A przeszukiwanie idzie do B, z B do D, z D do C, a z C do E, więc stos to A, B, D, C, E. Po drodze C widzi wierzchołek A, który wciąż jest na stosie: krawędź C–A zamyka cykl A, B, D, C. E nie ma nic nowego, więc jest przetworzony, potem C, a przeszukiwanie cofa się do D, który ma jeszcze F. Kolejność odwiedzin to A, B, D, C, E, F. Z celem E DFS kończy na ścieżce A → B → D → C → E, czyli czterech krawędziach, choć A → C → E ma tylko dwie.
Do czego się przydaje
Stos jest zawsze ścieżką od startu do bieżącego wierzchołka, dlatego DFS naturalnie pasuje do labiryntów i łamigłówek: na tym opierają się algorytmy z nawrotami (backtracking). W grafie nieskierowanym krawędź do wierzchołka, który wciąż jest na stosie, zamyka cykl. W grafie skierowanym wypisanie wierzchołków w kolejności odwrotnej do tej, w jakiej zostają przetworzone, daje porządek topologiczny, więc zadania wypadają po zadaniach, od których zależą. Przeszukiwanie w głąb znajduje też spójne składowe, mosty i punkty artykulacji, a jego losowa wersja to klasyczny sposób generowania labiryntów.
Historia
W XIX wieku francuski matematyk Charles Pierre Trémaux opisał sposób wyjścia z każdego labiryntu przez oznaczanie korytarzy – to przeszukiwanie w głąb wykonywane kredą. W latach 1972 i 1973 Robert Tarjan i John Hopcroft pokazali, że DFS rozwiązuje wiele problemów grafowych w czasie liniowym, od silnie spójnych składowych po sprawdzanie, czy graf da się narysować bez przecięć. W 1986 roku otrzymali Nagrodę Turinga, między innymi za tę pracę.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Wierzchołek, którego sąsiedzi są sprawdzani, jest wyróżniony, wierzchołki na stosie są niebieskie, a przetworzone zielone, każdy ze swoim numerem odwiedzin. Stos jest pokazany pod grafem, od startu do wierzchołka na szczycie. Obserwuj wiersz stanu, aby zobaczyć krawędzie zamykające cykl, i wybierz cel, aby zobaczyć, jak długa może być znaleziona ścieżka w porównaniu z przeszukiwaniem wszerz.
Często zadawane pytania
Jaka jest złożoność czasowa DFS?
O(V + E) dla V wierzchołków i E krawędzi: każdy wierzchołek raz trafia na stos i raz z niego schodzi, a każda krawędź jest sprawdzana z obu końców. Potrzeba O(V) dodatkowej pamięci na stos i oznaczenia.
Dlaczego DFS używa stosu?
Bo zasada „ostatni wchodzi, pierwszy wychodzi” sprawia, że przeszukiwanie idzie dalej od najnowszego wierzchołka i cofa się do poprzedniego. Rekurencja robi to samo za pomocą stosu wywołań programu. Gdyby zamiast stosu użyć kolejki, przeszukiwanie rozchodziłoby się pierścień po pierścieniu: to przeszukiwanie wszerz.
Czy rekurencyjny DFS to problem przy dużych grafach?
Może być: długa ścieżka oznacza głęboką rekurencję, a wiele języków ogranicza głębokość wywołań. Jawny stos w pętli omija ten limit i odwiedza wierzchołki w tej samej kolejności.
Gdzie używa się DFS?
Do rozwiązywania labiryntów i łamigłówek metodą nawrotów, znajdowania cykli, porządkowania zadań według zależności (sortowanie topologiczne), znajdowania spójnych i silnie spójnych składowych, generowania labiryntów oraz w kompilatorach i narzędziach do budowania, które przechodzą grafy zależności.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj przeszukiwanie w głąb