Depth-first search, vaak afgekort tot DFS, is een algoritme om een verbonden structuur zoals een boom of netwerk te verkennen. Het kiest één pad en volgt dat zo ver het kan, en pas als het op een doodlopend punt stuit, keert het terug om de volgende tak te proberen.
De duidelijkste analogie is een doolhof verkennen met één hand aan de muur. Je loopt door een gang tot die stopt, keert dan terug naar de laatste kruising en slaat een andere kant op. Je geeft je volledig over aan één route voor je een andere overweegt. Precies zo beweegt DFS door een binaire boom of een graaf: eerst diep, daarna breed. Zijn tegenhanger, breadth-first search, doet het omgekeerde door alles op één niveau te checken voor het dieper gaat.
DFS duikt op in genoeg echte software. Het lost puzzels op, bepaalt de juiste volgorde om softwarepakketten te installeren die van elkaar afhangen, en spoort lussen op in een netwerk van verbindingen. Omdat het diep duikt, gebruikt het weinig geheugen, maar het is niet ideaal als je de kortste route zoekt.
Een praktische valkuil is dat een pad eindeloos kan doorlopen. In een graaf met lussen draait DFS in cirkels tenzij het bijhoudt welke punten het al heeft bezocht, dus dat afvinken hoort bij een correcte uitvoering. Het wordt ook op twee manieren geschreven: met recursie, kort maar gevoelig voor een volle call stack bij een heel diepe structuur, of met een expliciete stack, die dat risico vermijdt tegen een paar regels extra.
Bij TopDevs kiezen we de juiste manier van doorlopen voor de klus bij functies als routing, aanbevelingen of afhankelijkheidschecks, zodat de code zowel snel als goed te volgen blijft.
