七十九、深度和广度优先搜索算法

@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。 ---- Runsen

深度优先搜索和广度优先搜索作为应用广泛的搜索算法，一般是必考算法。

深度优先算法（DFS）

深度优先算法的本质是回溯算法，多数是应用在树上，一个比较典型的应用就是二叉树的中序遍历。

DFS的实现考虑要以下几个问题即可：

①．边界范围：即搜索终止条件，递归结束条件。

②．可供选择的范围列表：所有可供选择的范围列表。

③．已做出的选择列表：标记当前已经做出的选择。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

根据深度优先搜索的特点，采用递归函数实现比较简单。

广度优先算法（BFS）

先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题，但是构建广度优先算法需要维护自己的队列。

比如，二叉树的层次遍历，我们大概会有如下几个步骤：

• 向Queue中放入root节点。
• 只要这个Queue中有元素就一直遍历。</

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/107182457