DFS, rekursjon og iterative stakker
Utforsk dypt og unngå rekursjonsgrenser
DFS, rekursjon og iterative stakker er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva DFS gjør
DFS går så dypt som mulig langs én vei, før den går tilbake og prøver den neste. Tenk på det som å utforske en labyrint gang for gang. 🧭
DFS vs. BFS
BFS sprer seg i ringer, mens DFS går i dybden først. Begge besøker alle nåbare noder, men i svært ulik rekkefølge.
Den rekursive strukturen
Rekursiv DFS merker en node som besøkt, og kaller deretter seg selv for hver ubesøkte nabo. Kallstakken husker hvor algoritmen skal returnere.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Merk før rekursjon
Sett besøkt-markeringen når en node nås, før naboene utforskes. Ellers kan sykler sende DFS inn i uendelig rekursjon.
Fellen med rekursjonsgrensen
Python begrenser rekursjon til rundt 1000 kall. En dyp graf utløser en RecursionError, som vises som en kjøretidsfeil.
Hev grensen
En rask løsning er å heve grensen med setrecursionlimit. Sett den høyere enn den maksimale dybden før DFS kjøres.
import sys
sys.setrecursionlimit(300000)Bruk iterativ DFS i stedet
Den tryggeste løsningen er en iterativ DFS med en egen stakk. Uten kallstakksdybde oppstår det aldri et rekursjonskrasj.
stack = [start]Ta ut fra stakken
Ta ut det øverste elementet fra stakken i hvert trinn. Sist inn, først ut gjør at DFS først går nedover den nyeste veien.
u = stack.pop()Legg naboene på stakken
Etter at u er tatt ut, legges hver ubesøkte nabo på stakken. Merk dem, slik at de ikke legges på nytt.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Den fullstendige iterative løkken
Gjenta uttak og innlegging så lenge stakken inneholder noder. Når den er tom, er alle nåbare noder besøkt.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Samme kostnad som BFS
I likhet med BFS besøker DFS hver node og kant én gang, og bruker derfor O(n + m). Velg algoritmen ut fra hvilken rekkefølge oppgaven krever.
Hurtigsjekk
Den rekursive DFS-en krasjer på en dyp graf. Hvorfor?
Oppsummering
De kan kjøre DFS rekursivt eller med en egen stakk, merke noder som besøkt ved inngang, og bytte til iterativ DFS når grafen blir dyp. 🎉
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «DFS, rekursjon og iterative stakker» gratis?
Ja – hele teksten i «DFS, rekursjon og iterative stakker» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «DFS, rekursjon og iterative stakker»?
Utforsk dypt og unngå rekursjonsgrenser Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «DFS, rekursjon og iterative stakker»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Naboskapslister fra inndata
- BFS for korteste uvektede stier
- DFS, rekursjon og iterative stakker
- Sammenhengende komponenter og flomfylling