Explain BFS and DFS in terms of backtracking
- by HH
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:
how do you define "Backtracking" GRAPH-theoretically?
what is "backtracking" in BFS and DFS?
