【参考答案】讨论6.3 试比较DFS和BFS的优点和缺点

<p>DFS的特点是“一条路跑到黑”。当我们运气不错，不需要试探几条路就能找到解的时候，DFS是不错的选择。它最招程序员喜欢的地方是可以用非常简单的递归实现 —— 是的递归需要额外的存储空间，但是无论如何都跟递归的深度成正比，而深度一般比BFS要搜索的宽度小多了。所以一次DFS用的空间跟一条搜索路径上顶点的个数成正比。如果问题是能找到一个解就可以了，那么用DFS碰碰运气吧~ 当然运气差的时候也得把所有可能的路径都找一遍。</p><p><br ></p><p>BFS的特点是层层扩散。如果问题是要找到一个距离出发点最近的解，那么BFS是最好的选择，因为它就是按照距离逐步递增的规律来搜索的，路上碰到的第一个解就一定是了。而这个问题如果用DFS就傻了，得把所有的解都找到，才敢确切地从里面挑一个最近的。当然另一方面，BFS需要程序员自己写个队列，代码比较长。而且这个队列要能同时存储一整层顶点 —— 简单地想象一棵满二叉树吧，每层顶点的个数可是呈指数级增长的！所以还没搜几层空间就会不够用了……</p><p><br ></p><p>当遇到一个具体问题的时候，选择哪种遍历可能需要掷骰子，因为我们事先并不知道解在哪里…… 个人建议是：需要找最优解的时候先考虑BFS，而大多数时候是DFS好用。</p><p><br ></p>