Depth-first search

Depth-first search (DFS) is een zoekalgoritme voor het doorzoeken van een boomstructuur of een graaf. Het algoritme begint bij de wortel (of eender welke knoop bij een graaf) en kiest een tak en doorzoekt deze zo ver mogelijk, zonder terug te keren op vorige stappen.

Overzicht

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, keert het algoritme terug tot het een kindknoop vindt die nog niet doorzocht is. In een niet-recursieve implementatie worden alle geopende knopen op een stack gezet, zodat deze later onderzocht kunnen 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 doorzocht moet worden. Beide algoritmen zijn O(|K| + |B|), met K het aantal knopen en B het aantal bogen.

Iteratief diepte-eerst zoeken

Zie Iterative deepening depth-first search voor het hoofdartikel over dit onderwerp.

Bij het doorzoeken van grote grafen die niet volledig in het geheugen passen, is het mogelijk dat oneindig lang gezocht moet worden omdat het pad oneindig lang lijkt. De eenvoudige oplossing om de knopen te kleuren die al bezocht zijn, is niet toepasbaar daar niet al deze knopen in het geheugen gehouden kunnen worden. Dit kan worden opgelost door iteratief de diepte te vergroten.

Zie de categorie Depth-first search van Wikimedia Commons voor mediabestanden over dit onderwerp.