Explain BFS and DFS in terms of backtracking

Question

Wikipedia about DFS

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 is BFS?

"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 continuos backtracking.

Regex, find's pruning -- backtracking?

The term backtracking confuseses due to its variety of use. UNIX find's 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 too wide umbrella-term. So:

1. how do you define "Backtracking" GRAPH-theoretically?
2. what is "backtracking" in BFS and DFS?

[Added]

Good defs about backtracking and examples

1. like brute-force-method
2. Stallman's (?) invented term "dependency-directed backtracking" --
3. backtracking and regex example
4. DFS def.

Answer 1

Picture someone driving down every street until he hits a dead end, and then backing up and trying the next street, again until he hits a dead end. Backtracking is when he has to turn the car around to get back out onto the road. With something like an array, it's easy to check each element, since it's linear. With a tree, you follow paths down either depth-first or breadth-first, and back out when you hit dead ends in order to follow the next path.

There is another, more specific definition: it's a problem-solving strategy where possibilities are checked recursively to see if they are a "partial solution." This more specific usage is what's going on with regular expressions.

Edit: what followed was a lengthy example of not backtracking but DFS with pruning :( I've pulled it since the two, while connected, are not the same thing.

These Stanford lectures by Julie Zelenski are wonderful:

Programming Abstractions, Lecture 10

Programming Abstractions, Lecture 11

She solves 8 queens, a sudoku puzzle, and a number substitution puzzle using recursive backtracking, and everything is nicely animated.

A graph theory explanation would follow from the fact that trees are a specific type of graph. In the simplest case, you backtrack from leaf nodes (terminal vertices) to the immediate parent. But if all of the possibilities down a particular branch have been tried, we backtrack to the parent of that branch's root node.