Diepte-eerst zoeken (DFS)
Doorzoekt een graaf door één pad zo diep mogelijk te volgen en dan terug te gaan naar de laatste splitsing. De stapel op het scherm is dat pad.
- tijd O(V + E)
- geheugen O(V)
- gebruikt een stapel
Wat betekent dit?
- Knoop: een punt van de graaf, hier getekend als een cirkel met een letter.
- Kant: een lijn die twee knopen verbindt. Je kunt hem hier in beide richtingen volgen.
- Buren: de knopen die via een kant met een knoop verbonden zijn. Ze worden in alfabetische volgorde bekeken.
- Wachtrij: wie het eerst komt, gaat het eerst. BFS neemt altijd de knoop die het langst heeft gewacht.
- Stapel: wat er het laatst op komt, gaat er het eerst af. DFS gaat altijd verder vanaf de knoop die het laatst is bereikt.
- V en E: het aantal knopen (vertices) en kanten (edges). O(V + E) betekent dat elke knoop en elke kant een vast aantal keren aan de beurt komt.
- op de stapel
- huidige
- afgerond
- kant van de zoekboom
- overgeslagen kant
Begin bij A. Druk op afspelen of doorloop de zoektocht stap voor stap.
Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.
Probeer dit: Kies de graaf met cycli. Elke gestreepte kant leidt terug naar een knoop die al op de stapel ligt of al is afgerond: die kant sluit een cyclus.
Hoe het werkt
DFS roept zichzelf aan op de eerste buur die het nog niet heeft gezien, dan op de eerste nieuwe buur daarvan, enzovoort. Heeft een knoop geen nieuwe buren meer, dan eindigt zijn aanroep en gaat DFS één stap terug om daar de volgende buur te proberen. De open aanroepen vormen een stapel, en die is altijd het pad van de start naar de huidige knoop. Het getal naast een knoop is de volgorde waarin hij is bezocht.
Wanneer het een goede keuze is
Gebruik DFS om uit te zoeken wat je überhaupt kunt bereiken, om cycli te vinden, om door een doolhof te lopen of om taken die van elkaar afhangen in de juiste volgorde te zetten. De kortste weg vindt het niet.