DFS与BFS是否可互换？二者求解能力是否等价？

核心结论 #

对于所有基于状态空间遍历的可计算问题，DFS和BFS的求解能力是完全等价的：不存在某类问题只能用DFS求解、无法用BFS得到正确结果的情况，反之亦然。二者的差异仅体现在时间/空间开销、代码实现便捷度层面，和“能不能解”无关。

等价性的严谨证明（构造性证明） #

DFS和BFS的核心框架完全一致，唯一区别仅为待遍历节点的存取规则：

• DFS依赖栈结构（递归实现时为程序自带的调用栈）存储待访问节点，遵循后进先出规则，优先沿单条路径遍历到最深状态再回溯
• BFS依赖队列结构存储待访问节点，遵循先进先出规则，优先遍历和初始状态距离（步数）相同的同层状态

证明过程：对任意一个可正确求解问题的DFS实现，保留其状态去重逻辑、状态转移规则、终止条件判断完全不变，仅将存储待访问节点的栈替换为队列，即可得到一个可正确求解同一问题的BFS实现。由于原DFS实现本身会覆盖所有可达状态、不会漏解，替换存取结构后的遍历逻辑依然会覆盖全部可达状态，必然能找到合法解。
反向证明同理：将正确BFS实现中的队列替换为栈，保留其余逻辑不变，即可得到正确的DFS实现。

这个构造性证明是完备的，不存在反例。

二者“适配场景差异”的本质 #

大家日常提到的“DFS适合某类题、BFS适合另一类题”，全部是效率和实现成本层面的最优解选择，和求解能力无关：

• 求解无权图最短路径类问题时，BFS首次触达目标节点即可得到最短路径，不需要遍历深层节点，时间效率最优；如果换DFS实现，需要遍历所有可达路径后比对长度才能得到最短结果，时间开销会高很多，但只要逻辑正确一定能算出准确答案
• 求解回溯类问题（排列组合、数独求解、约束满足类问题）时，DFS配合路径剪枝可以快速排除无效分支，递归实现代码量极小、栈内存开销低；如果换BFS实现，需要存储大量同层中间状态，内存很容易溢出，代码写起来也更繁琐，但只要内存足够、逻辑正确，同样能得到正确结果
• 很多入门资料会提到找环、拓扑排序等场景只能用DFS，这也是误区：BFS配合入度统计同样可以完成拓扑排序、检测有向图环，无向图场景下BFS记录访问来源节点也可以检测环，只是部分场景下实现复杂度比DFS高而已

需要注意的是，以上等价性仅针对有限状态空间、可通过访问标记去重的遍历场景；如果是无有效剪枝的无限状态空间问题，DFS和BFS都无法在有限时间内得到解，不存在某一种算法可以单独求解的情况。

内容的提问来源于stack exchange，提问作者Nathan