DFS, recursie en iteratieve stacks
Diep zoeken en recursielimieten vermijden
DFS, recursie en iteratieve stacks is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat DFS doet
DFS gaat zo diep mogelijk langs één pad en gaat daarna terug om het volgende pad te proberen. Denk aan het verkennen van een doolhof, gang voor gang. 🧭
DFS versus BFS
BFS verspreidt zich in lagen; DFS gaat eerst diep. Beide bezoeken elk bereikbaar knooppunt, maar in een heel andere volgorde.
De recursieve structuur
Recursieve DFS markeert een knooppunt als visited en roept zichzelf daarna aan voor elke nog niet bezochte buur. De aanroepstack onthoudt waar de uitvoering moet terugkeren.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Markeren vóór recursie
Stel visited in zodra je een knooppunt binnengaat, voordat je de buren verkent. Anders kunnen cycli DFS in oneindige recursie sturen.
De valkuil van de recursielimiet
Python beperkt recursie tot ongeveer 1000 aanroepen. Een diepe graaf veroorzaakt een RecursionError, die als runtimefout in het oordeel verschijnt.
De limiet verhogen
Een snelle oplossing is de limiet te verhogen met setrecursionlimit. Stel die vóór het uitvoeren van DFS hoger in dan de maximale diepte in het slechtste geval.
import sys
sys.setrecursionlimit(300000)Gebruik in plaats daarvan een iteratieve aanpak
De veiligste oplossing is een iteratieve DFS met je eigen stack. Zonder aanroepdiepte krijg je nooit een recursiecrash.
stack = [start]Van de stack verwijderen
Verwijder bij elke stap het bovenste element van de stack. Last in, first out zorgt ervoor dat DFS eerst het meest recente pad volgt.
u = stack.pop()De buren op de stack zetten
Zet na het verwijderen van u elke nog niet bezochte buur op de stack. Markeer ze zodat ze niet opnieuw op de stack worden gezet.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)De volledige iteratieve lus
Herhaal het verwijderen en toevoegen zolang de stack knooppunten bevat. Als de stack leeg is, is elk bereikbaar knooppunt bezocht.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Dezelfde kosten als BFS
Net als BFS bezoekt DFS elk knooppunt en elke kant één keer en draait het in O(n + m). Kies op basis van de volgorde die het beste bij de taak past.
Korte controle
Je recursieve DFS crasht op een diepe graaf. Waarom?
Samenvatting
Je voert DFS recursief uit of met je eigen stack, markeert knooppunten bij binnenkomst en schakelt over op een iteratieve aanpak wanneer de graaf diep wordt. 🎉
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “DFS, recursie en iteratieve stacks” gratis?
Ja — de volledige tekst van “DFS, recursie en iteratieve stacks” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “DFS, recursie en iteratieve stacks”?
Diep zoeken en recursielimieten vermijden Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “DFS, recursie en iteratieve stacks”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Adjacentielijsten uit invoer
- BFS voor kortste ongewogen paden
- DFS, recursie en iteratieve stacks
- Samenhangende componenten en flood fill