Depth-first search
Search algorithm / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Depth-first search?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
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.
This article needs additional citations for verification. (July 2010) |
Quick Facts Class, Data structure ...
Order in which the nodes are visited | |
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) |
Close
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]