Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
- 1 Formal definition
- 2 Example
- 3 Output of a depth-first search
- 4 Applications
- 5 See also
- 6 References
- 7 External links
Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn’t finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.
The time and
View original post 359 more words