Editing Depth-first search (section)

{{short description|Search algorithm}}
{{Refimprove|date=July 2010}}
{{Infobox algorithm
|class=[[Search algorithm]]
|image=Depth-first-tree.svg
|caption=A tree labeled by the order in which DFS expands its nodes
|data=[[Graph (data structure)|Graph]]
|time=<math>O(|V| + |E|)</math> for explicit graphs traversed without repetition, <math>O(b^d)</math> for implicit graphs with branching factor ''b '' searched to depth ''d''
|space=<math>O(|V|)</math> if entire graph is traversed without repetition, O(longest path length searched) =  <math>O(bd)</math>for implicit graphs without elimination of duplicate nodes
|complete=yes (unless infinite paths are possible)
|optimal=no (does not generally find shortest paths)
}}
'''Depth-first search''' ('''DFS''') is an [[algorithm]] for traversing or searching [[tree data structure|tree]] or [[graph (data structure)|graph]] data structures. The algorithm starts at the [[tree (data structure)#Terminology|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 (abstract data type)|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]]<ref>[[Charles Pierre Trémaux]] (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph <br /> 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}})</ref> as a strategy for [[Maze solving algorithm|solving mazes]].<ref>{{citation|title=Graph Algorithms|first=Shimon|last=Even|author-link=Shimon Even|edition=2nd|publisher=Cambridge University Press|year=2011|isbn=978-0-521-73653-4|pages=46–48|url=https://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46}}.</ref><ref>{{citation|title=Algorithms in C++: Graph Algorithms|first=Robert|last=Sedgewick|edition=3rd|publisher=Pearson Education|year=2002|isbn=978-0-201-36118-6}}.</ref>