Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Depth-first search
open-in-new
<p>Depth-first search (DFS) is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for traversing or searching <a href="/facts/Tree_data_structure/RcXz9noF">tree</a> or <a href="/facts/Graph_(data_structure)/b8qcddXa">graph</a> data structures. The algorithm starts at the <a href="/facts/Tree_(data_structure)/RcXz9noF">root node</a> (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 <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack</a>, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. </p><p>A version of depth-first search was investigated in the 19th century by French mathematician <a href="/facts/Charles_Pierre_Tr%25C3%25A9maux/T0uFMTHt">Charles Pierre Trémaux</a> as a strategy for <a href="/facts/Maze_solving_algorithm/3c1KTprw">solving mazes</a>. </p>