浅谈迷宫类问题中的BFS和DFS

最近刷了很多迷宫类问题的算法，这类题目普遍都是使用DFS和BFS来解决，那么DFS和BFS间到底有什么区别呢？

DFS，深度优先遍历，在整个函数递归的过程中，会找到所有可能的路径。比如说，一个迷宫问题有一些出口，DFS会将可到达这些出口的所有路径都遍历一遍，一个出口可能会对应多条路径。
所以，如果要统计整个迷宫中有多少条可行的不重复的路径，那么使用DFS是可行的。

BFS，广度优先遍历，是通过队列+循环实现的，它并不会找到所有可行的路径，实际上，对于每一个出口，如果存在可行路径，那么BFS最终找到的是到达这个出口的最短路径。因此，对于每一个存在可行路径的出口而言，BFS只会记录到这个出口的最短的那条路径。

所以，如果要统计整个迷宫中有几个出口或要求最短路径的话，使用BFS是可行的。

另外，BFS和DFS虽然都需要剪枝，但是DFS是需要回溯的，但是BFS不需要。