Terug naar begrippenlijst
Depth-First Search (DFS)
Depth-First Search (DFS) is een algoritme dat wordt gebruikt om door een boom of graaf (graph) te navigeren. Het werkt volgens een simpel maar krachtig principe: duik zo diep mogelijk één kant op, en ga pas terug als je vastloopt. DFS zoekt dus niet “laag voor laag” (zoals Breadth-First Search dat doet), maar volgt één pad tot het einde, en backtrackt dan om andere paden te verkennen. Het is een soort digitale speurtocht door knopen en verbindingen en het komt verrassend vaak van pas.
Inhoudsopgave
Eerst de diepte in, dan pas terug
Stel je een doolhof voor. DFS kiest een richting en blijft die volgen tot het niet verder kan. Pas dan keert het terug naar het vorige keuzepunt om een ander pad te proberen. Net zolang tot het doel is bereikt of alles is verkend.
In code gebeurt dit meestal via recursie (waarbij een functie zichzelf opnieuw aanroept), of met een stack (een datastructuur die het laatst bezochte punt bijhoudt). Daardoor is DFS relatief eenvoudig te implementeren, maar toch krachtig in zijn werking en breed toepasbaar in allerlei soorten software.
Voor puzzels, paden en programmeertrucs
DFS is ideaal als je:
- Snel een pad naar een oplossing wilt vinden (niet per se het kortste)
- Alles in een netwerk wilt doorlopen
- Structuren zoals puzzels, bomen of afhankelijkheden moet analyseren
- Wil checken of er cycli in een graaf zitten
Het algoritme is compact, efficiënt, en past in allerlei situaties: van spelontwikkeling tot compilerdesign.
Niet altijd de snelste, wél grondig
DFS is niet altijd de beste keuze. Het kan zich blindstaren op één pad dat eindeloos doorgaat (zeker in oneindige of cyclische grafen). En het vindt lang niet altijd het kortste pad.
Maar het is wel grondig. DFS komt uiteindelijk bij elke knoop, zolang je maar goed bijhoudt waar je al bent geweest. En met de juiste aanpassingen kun je het uitbreiden naar krachtige toepassingen, zoals topologische sortering of labyrintoplossers.
Veelgestelde vragen
DFS gaat eerst diep de structuur in; BFS (Breadth-First Search) verkent eerst alle knopen op hetzelfde niveau. BFS vindt meestal de kortste route, DFS verkent sneller diepere paden.
Nee, je kunt DFS ook implementeren met een stack in plaats van recursie. Dat is vaak efficiënter bij grote grafen.
Bijvoorbeeld in het doorlopen van bestanden/directories, dependency analysis, speloplossers, webcrawlers en meer.
Ja, als je geen visited-checks gebruikt. Altijd bijhouden waar je bent geweest!
Thijn de Haas Lead developer
Gerelateerde begrippen
- Abstraction
- Access Control
- Affiliate link
- AJAX
- Algoritme
- Apache
- API
- Big data
- Binary Tree
- Bitbucket
- Blockchain
- Bug
- Caching
- ChatGPT
- Cloudflare
- Codebase
- Content Delivery Network (CDN)
- Content Management Systeem
- Cookietijd
- Cross-Site Scripting (XSS)
- Customer Relationship Management (CRM)
- Database Management System (DBMS)
- Debugging
- Deep Learning
