<span>《算法竞赛进阶指南》【0X20搜索】</span>

这章最重要的两大知识点就是BFS和DFS了
首先，DFS方面要了解搜索树这一概念，知道了这个之后对于递归中的回溯操作会理解一些
BFS就是相当于边权为1的最短路，我们一般运用队列

0X21树与图的遍历

主要就是模板，其中包括了树的深度优先遍历，前序遍历，后序遍历，中序遍历。还有树的重心等知识点。还有图的广度优先遍历，拓扑排序。其中拓扑排序是重点，模板如下

void top_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i ++ ) {
        if (d[i] == 0) q.push(i);
    }
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        a[++ cnt] = t;//a用来存拓扑排序序列
        for (int i = h[i]; ~i; i = nex[i]) {//我们用邻接表来存图
            int j = val[i];
            d[j] -- ;
            if (d[j] == 0) q.push(j);
        }
    }
}

0X22深度优先搜索 & 0X23剪枝

DFS是离不开剪枝的，适当的剪枝可以让我们的DFS运行的更快不容易TLE
一般我们有这么几种剪枝方法
1、优化搜索顺序
2、排除等效的情况
3、适当的“预判”
4、最优问题中的最优剪枝
5、记忆化搜索

0X24迭代加深搜索

就是知道答案的深度不会太大，所以我们限制搜索深度从而找到最优解的情况
还有一个比较重要的知识点就是双向搜索，包括了双向DFS和我们等会会讲到的双向BFS

0X25广度优先搜索

主要理解的是走地图的模型，其他的BFS题目我们只要抽象成这个模型就比较好理解了

0X26广搜变形

这里讲到了很多的BFS变形，包括了双端队列BFS，其实就是边权为0和1的最短路问题
还有优先队列BFS相当于就是最短路问题
还有双向BFS，这个就是一个从起点开始扩展，一个从终点开始扩展，在中间相遇从而求得答案

0X27A*

A算法和IDA算法又叫做启发式搜索
因为二者都有一个启发函数
启发式函数相当于搜索中的剪枝，就是适当的“预判”
于是这两个最重要的点就是启发式函数应该如何求了