本文共 1473 字，大约阅读时间需要 4 分钟。

  搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。将所要解答的问题划分成若干个阶段或者步骤，当一个阶段计算完毕，下面往往有多种可选选择，所有的选择共同组成了问题的解空间。从根开始计算，到找到位于某个节点的解，深度优先搜索作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想，相当于采用了先根遍历的方法来构造搜索树。   对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）。搜索的要点：  （1）初始状态  （2）重复产生新状态  （3）检查新状态是否为目标，是结束，否转（2） 如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。 如果扩展是首先扩展新产生的状态，则叫深度优先搜索。

深度优先搜索DFS

  深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。每次深度优先搜索的结果必然是图的一个连通分量，深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的"结束时间"排序（具体做法是创建一个list，在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表)，则可以得到所谓的"拓扑排序"，即topological sort。利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先搜索用一个数组存放产生的所有状态。

（1） 把初始状态放入数组中，设为当前状态 （2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态 （3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态 （4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法 （5） 如果数组为空，说明无解 以上过程可以通过递归实现，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。

广度优先搜索BFS

  广度优先搜索（也称宽度优先搜索，缩写BFS）属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

DFS与BFS对比

  深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：

把根节点压入栈中。每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。   广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形： 把根节点放到队列的末尾。每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。

转载地址：http://uyhli.baihongyu.com/