搜索算法是利用计算机的高性能来有目的的穷举一问题解空间的部分或所有可能的情况，从而求出问题的解的一种方法。搜索算法有多种，其中深度优先搜索（DFS）和广度优先搜索（BFS）是两种最基本且常用的搜索算法。深度优先搜索（DFS）：基本思想：深度优先搜索是尽可能“深”地搜索树。为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。实现方式：深度优先搜索的实现方式可以采用递归或者栈来实现。算法步骤：初始化图中的所有节点为均未被访问。从图中的某个节点v出发，访问v并标记其已被访问。依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复步骤（2）和（3））。题目应用：全排列问题。基本思想是从初始状态生成搜索树下一层任一个结点，检查是否出现目标状态，若未出现，以此状态利用规则生成再下一层任一个结点，再检查，重复过程一直到叶节点（即不能再生成新状态节点），当它仍不是目标状态时，回溯到上一层结果，取另一可能扩展搜索的分支。采用相同办法一直进行下去，直到找到目标状态为止。广度优先搜索（BFS）：基本思想：类似树的按层遍历。首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。算法步骤：从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。最终结果：可能找到目标结点，也可能扩展完所有结点而没有找到目标结点。深度优先搜索与广度优先搜索的区别：遍历方式：深度优先搜索是尽可能“深”地搜索树，而广度优先搜索是类似树的按层遍历。所用数据结构：深度优先搜索的实现方式可以采用递归或者栈来实现，而广度优先搜索通常使用队列来实现。