DFS, rekurencja i stosy iteracyjne
Głębokie przeszukiwanie bez przekraczania limitów rekurencji
DFS, rekurencja i stosy iteracyjne to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Działanie DFS
DFS schodzi tak głęboko, jak to możliwe, jedną ścieżką, a następnie cofa się i próbuje kolejnej. Można wyobrazić sobie przechodzenie labiryntu korytarz po korytarzu. 🧭
DFS a BFS
BFS rozchodzi się warstwami, a DFS najpierw zagłębia się w jedną ścieżkę. Oba algorytmy odwiedzają każdy osiągalny wierzchołek, ale w zupełnie innej kolejności.
Rekurencyjna struktura
Rekurencyjny DFS oznacza wierzchołek jako visited, a następnie wywołuje siebie dla każdego nieodwiedzonego sąsiada. Stos wywołań pamięta, dokąd należy wrócić.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Oznaczanie przed rekurencją
Wartość visited należy ustawić przy wejściu do wierzchołka, przed rozpoczęciem odwiedzania sąsiadów. W przeciwnym razie cykle spowodują nieskończoną rekurencję.
Pułapka limitu rekurencji
Python ogranicza rekurencję do około 1000 wywołań. Głęboki graf powoduje błąd RecursionError, który pojawia się jako błąd wykonania programu.
Zwiększanie limitu
Jednym szybkim rozwiązaniem jest podniesienie limitu za pomocą setrecursionlimit. Należy ustawić go powyżej maksymalnej możliwej głębokości przed uruchomieniem DFS.
import sys
sys.setrecursionlimit(300000)Zamiast tego należy użyć wersji iteracyjnej
Najbezpieczniejszym rozwiązaniem jest iteracyjny DFS z użyciem własnego stosu. Brak głębokości wywołań oznacza, że nie wystąpi błąd przepełnienia rekurencji.
stack = [start]Pobieranie ze stosu
W każdym kroku należy pobrać element ze szczytu stosu. Zasada „ostatni wchodzi, pierwszy wychodzi” sprawia, że DFS najpierw zagłębia się w ostatnio wybraną ścieżkę.
u = stack.pop()Dodawanie sąsiadów na stos
Po pobraniu u należy dodać każdego nieodwiedzonego sąsiada na stos. Sąsiadów trzeba oznaczyć, aby nie dodać ich ponownie.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Pełna pętla iteracyjna
Należy powtarzać pobieranie i dodawanie, dopóki stos zawiera wierzchołki. Gdy się opróżni, wszystkie osiągalne wierzchołki będą odwiedzone.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Taki sam koszt jak BFS
Podobnie jak BFS, DFS odwiedza każdy wierzchołek i każdą krawędź raz, więc działa w czasie O(n + m). Należy wybrać algorytm zależnie od kolejności odpowiedniej dla danego zadania.
Szybkie sprawdzenie
Rekurencyjny DFS kończy się błędem na głębokim grafie. Dlaczego?
Podsumowanie
Algorytm DFS można uruchomić rekurencyjnie lub z użyciem własnego stosu, oznaczając wierzchołki przy wejściu i przechodząc na wersję iteracyjną, gdy graf jest głęboki. 🎉
Często zadawane pytania
Czy lekcja „DFS, rekurencja i stosy iteracyjne” jest bezpłatna?
Tak — pełny tekst „DFS, rekurencja i stosy iteracyjne” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „DFS, rekurencja i stosy iteracyjne”?
Głębokie przeszukiwanie bez przekraczania limitów rekurencji Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „DFS, rekurencja i stosy iteracyjne”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Listy sąsiedztwa z danych wejściowych
- BFS dla najkrótszych ścieżek nieważonych
- DFS, rekurencja i stosy iteracyjne
- Spójne składowe i flood fill