title: Explain BFS and DFS in terms of backtracking
body: <p><strong>Wikipedia about Depth First Search:</strong></p>
  <blockquote>
  <p>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
  <strong>each branch before backtracking.</strong></p>
  </blockquote>
  <p><strong>So what is Breadth First Search?</strong></p>
  <blockquote>
  <p>&quot;an algorithm that choose a starting
  node, checks all nodes <strong>backtracks</strong>,
  chooses the shortest path, chose neighbour nodes <strong>backtracks</strong>,
  chose the shortest path, finally
  finds the optimal path because of
  traversing each path due to continuous
  backtracking.</p>
  </blockquote>
  <p><strong>Regex <code>find</code>'s pruning -- backtracking?</strong></p>
  <p>The term backtracking confuses due to its variety of use. UNIX's <code>find</code> pruning an SO-user explained with backtracking. Regex Buddy uses the term &quot;catastrophic backtracking&quot; if you do not limit the scope of your Regexes. It seems to be a too widely used umbrella-term. So:</p>
  <ol>
  <li>How do you define &quot;backtracking&quot; specifically for Graph Theory?</li>
  <li>What is &quot;backtracking&quot; in Breadth First Search and Depth First Search?</li>
  </ol>
  <p><strong>[Added]</strong></p>
  <p><strong>Good definitions about backtracking and examples</strong></p>
  <ol>
  <li><a href="http://web.archive.org/web/20141109193758/http://web.cse.ohio-state.edu/%7Egurari/course/cis680/cis680Ch19.html" rel="nofollow noreferrer">The Brute-force method</a></li>
  <li>Stallman's(?) invented term <a href="http://web.archive.org/web/20130523233954/http://www.kerneltrap.org/node/4484" rel="nofollow noreferrer">&quot;dependency-directed backtracking&quot;</a></li>
  <li>Backtracking and <a href="http://web.archive.org/web/20090517003722/http://kerneltrap.org/node/16028" rel="nofollow noreferrer">regex</a> example</li>
  <li><a href="https://encyclopediaofmath.org/wiki/Depth-first_search" rel="nofollow noreferrer">Depth First Search definition.</a></li>
  </ol>