DFS和BFS

深度优先搜索(DFS)

和广度优先搜索一样，深度优先搜索（DFS）是用于在树/图中遍历/搜索的一种重要算法。

与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在DFS 中找到的第一条路径可能不是最短路径。

在DFS中，结点的处理顺序是完全相反的顺序，就像它们被添加到栈中一样，它是后进先出。所以深度优先搜索一般使用栈实现.

也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，
那么按照优先向着“深”的方向前进的策略，假如我们使用递归实现，我们的遍历过程为 1（起
始节点）->2（遍历更深一层的左子节点）->4（遍历更深一层的左子节点）->2（无子节点，返回
父结点）->1（子节点均已完成遍历，返回父结点）->3（遍历更深一层的右子节点）->1（无子节
点，返回父结点）-> 结束程序（子节点均已完成遍历）。如果我们使用栈实现，我们的栈顶元素
的变化过程为 1->2->4->3。

深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍
历且父节点不同，则说明有环。也可以用之后拓扑排序判断是否有环路，若最后存
在入度不为零的点，则说明有环。
有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这
种做法叫做状态记录或记忆化（memoization）。

回溯法（backtracking）

是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状 态的深度优先搜索。

通常来说，排列、组合、选择类问题使用回溯法比较方便。

顾名思义，回溯法的核心是回溯。

1、在搜索到某一节点的时候，如果我们发现目前的节点（及
其子节点）并不是需求目标时

2、我们回退到原来的节点继续搜索，并且把在目前节点修改的状态 还原。

3、这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存
状态。

4、在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节 点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点 状态]。

可以记住两个小诀窍，一是按引用传状态，二是所有的状态修 改在递归完成后回改。

回溯法修改一般有两种情况，一种是修改最后一位输出，比如排列组合；一种是修改访问标
记，比如矩阵里搜字符串。

广度优先搜索（BFS）

是一种遍历或搜索数据结构（如树或图）的算法，也可以在更抽象的场景中使用。

广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它的特点是越是接近根结点的结点将越早地遍历,一层层进行遍历的，结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出,所以广度优先搜索一般使用队列实现。

考虑如下一颗简单的树。我们从 1 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，
那么按照优先向着“广”的方向前进的策略，队列顶端的元素变化过程为 [1]->[2->3]->[4]，其中
方括号代表每一层的元素。

由于是按层次进行遍历，广度优先搜索时按照“广”的方向进行遍历的常常用来处理最短路径等问题

图注