Depth-first Search
A depth-first search (DFS) is an algorithm for traversing a finite graph. DFS visits the child nodes before visiting the sibling nodes; that is, it traverses the depth of any particular path before exploring its breadth. A stack (oftentimes the program's call stack via recursion) is generally used when implementing the algorithm.
The algorithm begins with a chosen "root" node; it then iteratively transitions from the current node to an adjacent, unvisited node, until it can no longer find an unexplored node to transition to from its current location. The algorithm then backtracks along previously visited nodes, until it finds a node connected to yet more uncharted territory. It will then proceed down the new path as it had before, backtracking as it encounters dead-ends, and ending only when the algorithm has backtracked past the original "root" node from the very first step.
DFS is the basis for many graph-related algorithms, including topological sorts and planarity testing.
Read more about this topic: Graph Traversal, Graph Traversal Algorithms
Famous quotes containing the word search:
“The meaning of the Street in all ways and at all times is the need for sharing life with others and the search for community.”
—Virginia Hamilton (b. 1936)