DFS 和 BFS 可以互换吗？

Question

我知道 DFS 对某些问题有好处，而 BFS 对其他一些问题有好处，但如果可以使用 DFS 解决某些问题，是否可以用 BFS 解决（可能不太理想）（反之亦然）？有证据吗？谢谢！

Answer 1

不。

最短路径是可以使用 BFS 轻松解决的典型示例。但是使用 DFS，您要么必须接受无限循环的可能性，要么避免重新访问节点并且在许多情况下无法找到最短路径。

相反的例子就更难找到了。但例如，用于平面性测试的Hopcroft-Tarjan算法依赖于这样一个事实：在 DFS 中，您知道到当前节点的整个路径的属性。而 BFS 中没有这种上下文。