【算法基础】回溯算法和DFS(深度优先搜索)到底有什么区别？_深搜与回溯的区别

• DFS

DFS 英文名，Depth First Search，中文名 深度优先搜索，是图的一种搜索算法，每一个可能的分支路径深入到不能再深入为止，且每个节点只能访问一次。

深度优先搜索算法跟图结构紧密相关，任何涉及深度度优先搜索的问题，都伴随着图。

深度度优先搜索的能够在图结构里搜索到通往特定终点的一条或者多条特定路径。

• 回溯

回溯算法是系统地搜索问题的解的方法。

某个问题的所有可能解的称为问题的解空间，若解空间是有限的，则可将解空间映射成树结构。

任何解空间可以映射成树结构的问题，都可以使用回溯法。

回溯法是能够在树结构里搜索到通往特定终点的一条或者多条特定路径。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。

值得注意，回溯法以深度优先搜索的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

• 总结

因此，回溯算法 = 深度优先搜索 + 剪枝函数 这一说法并没有错。但这一结论也并不十分正确。

诚然，如上面所言，深度优先搜索是特定于图结构的一种搜索算法，回溯算法是特定于树结构的搜索算法。

那为何 回溯算法 = 深度优先搜索 + 剪枝函数这一说法没有错？

因为树是特殊的图。简单来说，树是广义的图。再简单来说，树是图。

因此，回溯算法与深度优先搜索的关系也昭然若揭。因为，实施算法的对象（数据结构）都是图，所以，两者可以相提并论，存在一些共性，回溯算法也得以在搜索时使用深度优先算法。

也显而易见，回溯算法 也并不简单的可以说回溯算法 = 深度优先搜索 + 剪枝函数。

因为并不是所有图都是树。

深度优先搜索适用于所有图。而回溯算法只适用于树结构。

任何解空间可以映射成树结构的问题，都可以使用回溯法。任何解空间不能映射成树结构的问题，都不可以使用回溯法。

说到这里，大概也弄明白了两者的关系。

陈述一个比较正确的结论：

回溯算法 = 树的深度优先搜索 + 剪枝函数

还需要强调的是，递归不递归跟算法毫无关系，递归只是算法的实现方式、算法代码化的手段。

另外注意，任何递归形式的算法都能通过栈、队列等数据结构转化为非递归的形式。

最后再说一句，思想不思想、方式不方式、具体不具体、状态不状态跟算法也毫无关系。

算法说思想、方式、具体、状态，人说格局、态度。

很高大上，但没啥用，没任何内涵跟意义。

一切解决特定问题的步骤的描述统称为算法。

回溯算法 跟 深度优先搜索算法都很经典，同为经典算法必须掌握。它们的区别跟关联都在于它们的数据结构，回溯算法是树结构，深度优先搜索是图结构。树与图的相似点跟不同点导致了回溯算法跟深度优先搜索算法的存在相似点、也存在不同点。

参考资料：

[1] 回溯算法和DFS(深度优先搜索)到底有什么区别？