depth-first-search - 伪代码中的回溯深度优先搜索算法

Question

boolean backtrackDFS(v)  {
   If  (SolutionFound(v))  return true;
   Mark vertex v as reached.
   for (each unreached vertex u adjacenct from v)
        if (backtrakDFS(u)) return true;
   Unmark vertex v; 
   return false;
}

这里为什么Unmark vertex v需要？为什么添加这样的行是安全的，因此 v 再次无法访问，会导致重新访问吗？

Answer 1

我认为不需要。通常最好的做法是撤消所做的事情，让事情保持原样。

例如，包括该行将允许您多次使用相同的功能进行搜索，而无需单独的操作来清除标记。