Diepte-eerst zoeken (DFS)

Loop een doolhof in, ga door tot je vastloopt, ga dan terug naar de laatste splitsing en probeer de volgende weg. Zo verkent diepte-eerst zoeken een graaf. Het is een van de eenvoudigste graafalgoritmen, en de stapel die het bijhoudt vertelt je meer dan je zou verwachten.

Een graaf met een lange keten knopen vanaf de start geel gemarkeerd, afgeronde knopen lichtpaars, en de stapel als een rij vierkantjes eronder
Een graaf met een lange keten knopen vanaf de start geel gemarkeerd, afgeronde knopen lichtpaars, en de stapel als een rij vierkantjes eronder

Het idee

Een graaf is een verzameling knopen verbonden door kanten: kamers en deuren, webpagina's en links, taken en de taken waarvan ze afhangen. Diepte-eerst zoeken bezoekt elke knoop die het vanaf een start kan bereiken, maar in een bepaalde volgorde: het gaat altijd verder vanaf de knoop die het het laatst bereikte. Het houdt een stapel bij van de knopen waar het in zit. Een nieuwe knoop gaat bovenop, en een knoop gaat er pas af als alles eromheen verkend is.

Stap voor stap

Zet de start op de stapel en geef hem bezoeknummer 1. Bekijk de volgende buur van de knoop bovenaan. Is die nog niet gezien, geef hem dan het volgende bezoeknummer, onthoud de knoop vanwaar hij bereikt is, en zet hem bovenop de stapel. Is hij al eerder gezien, sla hem dan over. Als de knoop bovenaan geen buren meer heeft om te bekijken, is hij afgerond: haal hem eraf en ga verder met de knoop eronder. Stop als de stapel leeg is, of als het doel bereikt is.

Een voorbeeld

Neem een graaf met de kanten A–B, A–C, B–D, C–D, C–E en D–F, start bij A, en bekijk buren in alfabetische volgorde. Vanuit A gaat het zoeken naar B, vanuit B naar D, vanuit D naar C, en vanuit C naar E, dus de stapel is A, B, D, C, E. Onderweg ziet C de knoop A, die nog op de stapel ligt: de kant C–A sluit de cykel A, B, D, C. E heeft niets nieuws, dus is afgerond, daarna C, en het zoeken gaat terug naar D, die nog F heeft. De bezoekvolgorde is A, B, D, C, E, F. Met E als doel stopt DFS met het pad A → B → D → C → E, vier kanten, terwijl A → C → E er maar twee nodig heeft.

Waar het goed voor is

De stapel is altijd een pad van de start naar de huidige knoop, en daarom past DFS goed bij doolhoven en puzzels: het is het idee achter backtracking. In een graaf zonder richtingen sluit een kant naar een knoop die nog op de stapel ligt een cykel. In een graaf met richtingen geeft het opsommen van de knopen in omgekeerde volgorde van afronden een topologische ordening, zodat taken na de taken komen waarvan ze afhangen. Diepte-eerst zoeken vindt ook samenhangende componenten, bruggen en articulatiepunten, en de willekeurige variant is een klassieke manier om doolhoven te maken.

Geschiedenis

In de 19e eeuw beschreef de Franse wiskundige Charles Pierre Trémaux een manier om uit elk doolhof te ontsnappen door gangen te markeren: diepte-eerst zoeken met krijt. In 1972 en 1973 lieten Robert Tarjan en John Hopcroft zien dat DFS veel graafproblemen in lineaire tijd oplost, van sterk samenhangende componenten tot de vraag of een graaf zonder kruisingen getekend kan worden. Ze kregen in 1986 de Turing Award, deels voor dat werk.

Robert Tarjan, die in 1972–73 met John Hopcroft aantoonde dat diepte-eerst zoeken veel graafproblemen in lineaire tijd oplost; ze kregen de Turing Award van 1986 deels voor dat werk.
Robert Tarjan, die in 1972–73 met John Hopcroft aantoonde dat diepte-eerst zoeken veel graafproblemen in lineaire tijd oplost; ze kregen de Turing Award van 1986 deels voor dat werk.

Probeer het zelf

Open de app en druk op Stap. De knoop waarvan de buren worden bekeken is gemarkeerd, knopen op de stapel zijn blauw, en afgeronde knopen zijn groen, elk met zijn bezoeknummer. De stapel staat onder de graaf, van de start tot de knoop bovenaan. Let op de statusregel voor de kanten die een cykel sluiten, en kies een doel om te zien hoe lang het gevonden pad kan zijn vergeleken met breedte-eerst zoeken.

Veelgestelde vragen

Wat is de tijdcomplexiteit van DFS?

O(V + E) voor V knopen (vertices) en E kanten: elke knoop gaat één keer op en van de stapel, en elke kant wordt vanaf beide uiteinden bekeken. Het heeft O(V) extra geheugen nodig voor de stapel en de markeringen.

Waarom gebruikt DFS een stapel?

Omdat laatst erin, eerst eruit het zoeken laat verdergaan vanaf de nieuwste knoop en laat teruggaan naar de knoop ervoor. Recursie doet hetzelfde met de aanroepstapel (call stack) van het programma. Met een wachtrij in plaats daarvan zou het zoeken zich ring na ring uitbreiden: dat is breedte-eerst zoeken.

Is recursieve DFS een probleem bij grote grafen?

Dat kan: een lang pad betekent diepe recursie, en veel talen beperken hoe diep aanroepen kunnen gaan. Een expliciete stapel in een lus omzeilt die grens en bezoekt de knopen in dezelfde volgorde.

Waar wordt DFS gebruikt?

Bij doolhoven en puzzels oplossen met backtracking, cykels vinden, taken ordenen naar hun afhankelijkheden (topologisch sorteren), samenhangende en sterk samenhangende componenten vinden, doolhoven maken, en in compilers en buildtools die afhankelijkheidsgrafen doorlopen.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer diepte-eerst zoeken