DFS和回溯有什么区别

Question

我对 DFS 和回溯算法的区别感到困惑。 在我看来，Backtracking只是一个特殊版本的DFS，对吗？

Answer 1

回溯算法递归遍历搜索树，从根向下，深度优先。在每个节点 c，算法 检查 c 是否可以完成一个有效的解决方案 。 如果不能，则跳过以 c 为根的整个子树（修剪）。否则，算法检查 c 本身是否是一个有效的解决方案，如果是，则将其报告给用户；并递归枚举c的所有子树。两个测试和每个节点的子节点由用户给定的过程定义。

深度优先搜索 (DFS) 从根开始（在图的情况下选择任意节点作为根）并且 探索到最远在回溯之前尽可能沿着每个分支。