算法导论——DFS、BFS

DFS（Depth First Search）为**深度优先搜索**，也就是说**先尽量向下搜索**，若无法继续搜索，则向上回溯 DFS的思路再简单不过，但是时间复杂度**十分玄学**，大致是$O \left ( n^3 \right )$左右，也就是说，DFS**很容易被卡**，这时候就需要**剪枝** 剪枝有很多种，主要分为：**可行性剪枝、最优性剪枝和记忆化搜索** 可行性剪枝是指将**不合法的给去掉**，并没有难度，但是效率**不错** 最优性剪枝是指将**比当前答案还不好的给去掉**，有一定难度，效率**奇高** 记忆化搜索则是最**高效的**，其效率远远大于前面两者，但是**空间会变得很大**，这就是**空间换时间**，时间也就大致相当于空间，这样不会TLE，也基本不用担心MLE，可以说是**几乎完美了** BFS（Breadth First Search）为**广度优先算法**，**先搜索同层的，再搜索下一层** BFS的剪枝比DFS要多两样：**队列优化和双向BFS** 队列优化顾名思义，是使用**队列优化BFS** 而双向BFS则是**在一端BFS的同时，另一端也进行BFS，轮流进行，更容易找到答案**，这样的话，**效率会提升许多**，非常实用 BFS码量大，但是**由于其无需递归，所以效率会高一些**