波波老师，dfs中的回溯算法是不是自带的就有回溯的

Question

回溯算法是dfs自带的，还是要加上类似vis[]数组改变状态才是回溯

Answer 1

liuyubobobo 2020-10-05 14:48:21

在很多情况下，回溯和 DFS 这两个词可以互换使用的。实际上我认为这两个概念没必要仔细区分，但如果严格说：

回溯算法是一种解决问题的策略，说白了就是进行暴力搜索，在搜索过程中，如果遇到“问题”，就返回，所谓的“回溯”的“回”；

而 dfs 是一种具体的代码实现；

我不认为加上 vis[] 数组才叫回溯。加不加数组的关键，是你的搜索空间到底是树状的，还是图状的；

如果是树状的，并不需要 vis[] 数组，也可以完成一个回溯算法；

但如果是图状的，就必须有 vis[] 数组，因为对于图来说，可能出现节点的重复搜索的问题。

继续加油！：）