Explain BFS and DFS in terms of backtracking
Posted
by HH
on Stack Overflow
See other posts from Stack Overflow
or by HH
Published on 2010-04-25T16:57:16Z
Indexed on
2010/04/25
17:03 UTC
Read the original article
Hit count: 504
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?
© Stack Overflow or respective owner
