Wikipedia about Depth First Search:
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.
So what is Breadth First Search?
"an algorithm that choose a starting node, checks all nodes backtracks, chooses the shortest path, chose neighbour nodes backtracks, chose the shortest path, finally finds the optimal path because of traversing each path due to continuous backtracking.
Regex find
's pruning -- backtracking?
The term backtracking confuses due to its variety of use. UNIX's find
pruning an SO-user explained with backtracking. Regex Buddy uses the term "catastrophic backtracking" if you do not limit the scope of your Regexes. It seems to be a too widely used umbrella-term. So:
- How do you define "backtracking" specifically for Graph Theory?
- What is "backtracking" in Breadth First Search and Depth First Search?
[Added]
Good definitions about backtracking and examples
- The Brute-force method
- Stallman's(?) invented term "dependency-directed backtracking"
- Backtracking and regex example
- Depth First Search definition.