Depth-first search

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Volgorde waarin de knopen van de graaf bekeken worden

Depth-first search (DFS) is een zoekalgoritme voor het doorzoeken van een boomstructuur of een graaf. Hierbij beginnen we bij de wortel (of eender welke knoop bij een graaf) en we kiezen een tak en doorzoeken deze zo ver mogelijk zonder terug te keren op onze stappen.

Overzicht[bewerken]

Formeel gezien is DFS een ongeïnformeerde zoekmethode die bij de eerste kindknoop begint en dieper en dieper zoekt tot het de doelknoop gevonden heeft of tot er geen kinderknopen meer zijn. Als er geen kinderknopen meer zijn, keren we terug tot we een kindknoop vinden die we nog niet doorzocht hebben. In een niet-recursieve implementatie worden alle geopende knopen op een stack gezet zodat deze later kunnen onderzocht worden.

De ruimtelijke complexiteit is heel wat minder dan bij een breadth-first search. De tijdscomplexiteit van beide algoritmen hangt af van het aantal knopen en het aantal bogen (verbindingen) dat ze moeten doorzoeken. Beide algoritmen zijn O(|K| + |B|), met K het aantal knopen en B het aantal bogen.

Iteratief diepte-eerst zoeken[bewerken]

Nuvola single chevron right.svg Zie Iterative deepening depth-first search voor het hoofdartikel over dit onderwerp.

Als we grote grafen doorzoeken die niet volledig in het geheugen passen, is het mogelijk dat we oneindig lang zoeken omdat het pad oneindig lang lijkt. De eenvoudige oplossing om de knopen te kleuren die we al bezocht hebben is niet toepasbaar daar we niet al deze knopen in het geheugen kunnen houden. We kunnen dit oplossen door iteratief de diepte te vergroten.

Bronnen, noten en/of referenties