深度优先搜索与广度优先搜索

  • 用来处理多分支结构
  • 对于现行问题或单分支结构的问题。不适用深度搜索和广度搜索

1 深度搜索

  • 深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
  • 深度优先搜索与回溯剪枝这两个思想有一个非常重要的优势。它是一条路经走到黑。如果这条路径合适的话，就可以直接返回。另外。当前所有的搜索选项中，只有一条路径在工作。也就是说只需要记录当前一条路径的状态。所以解决迷宫问题的时候，不需要复杂的状态记录方法。只需要记录当前这一个分支的路径状态即可。

2 广度搜索

  • 广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

3 深搜广搜与其他算法思想

与蛮力法

  • 蛮力法的深搜和广搜。用来搜索树和图中满足条件的节点值。与前置节点或者后置节点没有必然的关系。即一般无后效性，前直接点不会影响后置节点的解。

与回溯剪枝的结合

  • 回溯剪枝与深搜结合。一般用来搜索满足条件的路径。与前置节点和后置节点有必然联系。一般具有多米诺性质,叶子节点的解一定满足其父节点。叶子结点为真则父节点一定为真。同理父节点为假则叶子结点一定为假（逆否命题）。用父节点为假的情况进行剪枝操作。

与分治限界的结合

  • 分支限界与广搜结合。一般用来搜索满足条件的路径。与前置节点和后置节点有必然联系。一般具有多米诺性质。

与递归和迭代思想的结合

参考递归和迭代的章节。