Tiefensuche

Tiefensuche (, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Im Gegensatz zur Breitensuche wird bei der Tiefensuche zunächst ein Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden. Für Graphen mit potentiell wenigen, langen Pfaden bietet sich die beschränkte Tiefensuche an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird.