DFS和回溯的区别是什么

Question

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

Answer 1

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

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