用BFS还是DFS?

Question

bobo老师，我记得你的图论课程中说过，譬如联通分量问题等既可以用BFS，也可以用DFS解决。但是DFS一般用递归方式实现，但是貌似我们并没有很强调递归的缺陷：栈溢出问题？ 而且，在leetcode上用DFS提交时，也没有碰到过栈溢出的问题。所以我想问，啥时候需要担心使用DFS会栈溢出呢？如果栈溢出的确是个问题，那是不是说BFS比DFS更好呢？毕竟不用担心栈溢出。。谢谢

Answer 1

liuyubobobo 2022-04-20 01:45:29

在面试中，如果你的第一直觉是写 DFS 方便，就写DFS；当然，如果第一直觉是需要写 BFS，那就写 BFS。99.99% 的情况，不需要考虑递归的栈溢出问题。剩下的 0.01% 的情况，可以在真的遇到栈溢出的情况下，再去改。因为其实太少见了，所以在面试中，这不是一个 concern，核心还是先写出一版可以正确解决问题的代码，有需要再去优化。

对于现代计算机的上层开发，在大多数情况下，尤其是业务层的开发，递归并不是一个 concern。但并不排除在一些特殊情况下（如底层的基础设施开发，或者嵌入式开发中），需要考虑递归的额外消耗。但整体依然可以采用这一原则：如果觉得写递归比写非递归方便得多（通常就是这个原因，所以才使用递归），那么就先实现一版递归代码，然后再优化。

不需要，甚至是不应该在第一时间去考虑优化的事情，而应该首先保证正确完成逻辑，是软件工程的重要原则。

继续加油！：）