第5章　深度优先遍历和广度优先遍历

根据搜索方式的不同，搜索算法大致可以分为深度优先遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）。以树为例，DFS的思路是沿着子树尽可能深地搜索树的分支，到达叶子节点后通过回溯重复上述过程，直到所有的节点都被访问。BFS的思路则是一层一层地访问节点，直到完成遍历。

由于DFS和BFS的这种差异，BFS一般用来求解最短问题（dijkstra算法的特例），而DFS书写起来比较简单，因此对于不是最短问题的情况，我们优先考虑使用DFS。然而事无绝对，DFS 也可以解决最短问题，但是要注意栈溢出的问题。在很多情况下，两者可以交替使用，比如本章要讲的岛屿问题。

不管是DFS还是BFS，本质上都是搜索，而这样的搜索通常来说都是暴力搜索，因此当需要对问题的所有可能情况进行穷举时，我们就应该想到DFS和BFS。而第16章要讲解的回溯法，也是DFS的一种，即也是一种暴力搜索方法，只不过回溯法会涉及前进和回溯的过程。