Back البحث المتعمق الأول Arabic Diafnsuach BAR Обхождане в дълбочина Bulgarian Cerca en profunditat Catalan Prohledávání do hloubky Czech Tiefensuche German Αναζήτηση κατά βάθος Greek Búsqueda en profundidad Spanish Sügavuti otsing Estonian Sakonera bilaketa Basque
 | This article needs additional citations for verification. (July 2010) |
 A tree labeled by the order in which DFS expands its nodes | |
| Class | Search algorithm |
|---|---|
| Data structure | Graph |
| Worst-case performance | for explicit graphs traversed without repetition, for implicit graphs with branching factor b searched to depth d |
| Worst-case space complexity | if entire graph is traversed without repetition, O(longest path length searched) = for implicit graphs without elimination of duplicate nodes |
| Optimal | no (does not generally find shortest paths) |
Preview warning: Page using Template:Infobox algorithm with unknown parameter "complete"
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.
A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux[1] as a strategy for solving mazes.[2][3]
- ^ Charles Pierre Trémaux (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph
in Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN 0980-6032) - ^ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.
- ^ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6.