A search algorithm of a tree that explores the first child of a node before visiting its siblings. Tarjan (1972) and Hopcroft and Tarjan (1973) showed that depth-first search gives linear-time algorithms for many problems in graph theory (Skiena 1990).
Depth-First Traversal
See also
Breadth-First TraversalExplore with Wolfram|Alpha
References
Hopcroft, J. and Tarjan, R. "Algorithm 447: Efficient Algorithms for Graph Manipulation." Comm. ACM 16, 372-378, 1973.Pemmaraju, S. and Skiena, S. "Depth-First Search." §7.1.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 280-282, 2003.Skiena, S. "Breadth-First and Depth-First Search." §3.2.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 95-97, 1990.Tarjan, R. E. "Depth-First Search and Linear Graph Algorithms." SIAM J. Comput. 1, 146-160, 1972.Referenced on Wolfram|Alpha
Depth-First TraversalCite this as:
Weisstein, Eric W. "Depth-First Traversal." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Depth-FirstTraversal.html