Nederlands
Menu

Wat is Diepte-eerst zoeken (depth-first search)?

Manier om een graaf of boom te doorzoeken die langs één pad zo ver mogelijk gaat en terugkeert om een ander pad te proberen als ze vastloopt. Ze wordt geïmplementeerd met recursie of een stack en wordt gebruikt om doolhoven op te lossen, samenhangende componenten en cykels te vinden, en voor topologisch sorteren. Afgekort als DFS.

Japanse benaming: 深さ優先探索

“Diepte-eerst zoeken (depth-first search)” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Diepte-eerst zoeken (depth-first search)

In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwoord en toelichting tonen

Antwoord: C. A, B, D, E, F, C

Vanuit A gaat de zoekactie naar B en dan naar D, de eerste onbezochte buur van B. De enige buur van D, B, is al bezocht, dus de zoekactie keert terug naar B en gaat verder naar E, dan van E naar de onbezochte F en van F naar haar buur C. De volgorde is dus A, B, D, E, F, C. A, B, C, D, E, F is de volgorde van breedte-eerst zoeken, dat de dichtstbijzijnde knopen eerst bezoekt. A, B, D, E, C, F keert bij E terug zonder naar de onbezochte F te gaan en is dus geen volgorde van diepte-eerst zoeken.

“Diepte-eerst zoeken (depth-first search)” in de toelichting

Vragen met “Diepte-eerst zoeken (depth-first search)” (3)

  1. In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?
  2. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  3. Voor de taken A tot E gelden de volgordebeperkingen „A vóór C”, „B vóór C”, „C vóór D”, „B vóór E” en „E vóór D”. Welke volgorde voldoet aan alle beperkingen (een resultaat van topologisch sorteren)?

Verwante termen

Recursie Breedte-eerst zoeken (breadth-first search) Wachtrij (queue) Stack (stapelgeheugen) Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Dynamisch programmeren (dynamic programming) Gelinkte lijst (linked list)

Naar de woordenlijst