Tiefensuche

Also known as DFS, depth-first traversal, depth first search, depth-first search

Suchalgorithmus in der Informatik (Graphentheorie)

Key facts

Class: Search algorithm
Data structure: Graph
Worst case performance: O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} for explicit graphs traversed without repetition, O ( b d ) {\displaystyle O(b^{d})} for implicit graphs with branching factor b searched to depth d
Worst case space complexity: O ( | V | ) {\displaystyle O(|V|)} if entire graph is traversed without repetition, O(longest path length searched) = O ( b d ) {\displaystyle O(bd)} for implicit graphs without elimination of duplicate nodes
Optimal: no (does not generally find shortest paths)

via Wikipedia infobox

Described at

Depth first search - Wikimedia Commons

commons.wikimedia.org →

Link to a page describing this subject · 937 chars · not written by Vinony

Wikidata facts

Subclass of: graph traversal
Image: Depth-first-tree.svg

Show 7 more facts

Commons category: Depth-first search
uses: LIFO
short name: DFS
maintained by WikiProject: WikiProject Mathematics
used by: intelligent agent
Commons gallery: Depth first search
described at URL: commons.wikimedia.org/wiki/Depth_first_search

Sources (2)

via Wikidata · CC0

Article · Deutsch

Tiefensuche (englisch depth-first search, 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 potenziell wenigen, langen Pfaden bietet sich die beschränkte Tiefensuche an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird. Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche.

Abstract from DBpedia / Wikipedia · CC BY-SA