本内容来源于算法基础课
搜索
对于一棵树进行搜索，遇到叶节点时进行回溯
深度优先搜索(DFS)
以当前节点为根节点的子树，若未完全遍历，则向下搜索；否则，回溯到父节点
数据结构
栈
空间复杂度
最多存储从根节点到叶节点路径上的所有点，即树的高度，$O(h)$
思路
考虑树的形式进行遍历，关键在于遍历的顺序
注意：
1. 回溯：恢复现场
2. 剪枝：在搜索过程中由于某些条件，停止搜索，直接回溯
path 用于记录路径:
- 使用全局遍历，在每一层搜索时维护
path，即进入时增加 ，回溯时删除 - 使用
path作为dfs的参数，进入时将对应增加的path传入参数
void dfs() { // 参数 传递给下一个节点的信息
if () {// 搜索到叶节点（递归出口）
} else { // 选取
for () { // 所有可能的分支
if () { // 满足条件，则遍历可能的向下一个节点
// 标记状态
dfs() // 搜索下一层节点
// 恢复现场
}
}
}
}
宽度优先搜索(BFS)
搜索当前层，遍历完成后，向下搜索一层
数据结构
队列
空间复杂度
最多存储叶节点上的一层的所有点，即树的宽度，$O(2^h)$
特点
当边的权重为1时，第一遇到的路径为最短路，因为会首先搜索所有距离为1的点，然后搜索距离更大的点
dp是没有环的最短路
q[++tt] = 1;// 初始化队列,加入初始元素
for (int i = 0; i < n; i++) d[i] = -1;// 初始化距离
while (q.notEmpty) {
int t = q[hh++]; // 弹出队头
//扩展t
if () { // 将满足条件的点加入队列中，通常使用距离标记只访问一次 d != -1
// 更新距离
// 加入队列
}
}
// return 目标状态距离
注意：
为了防止一个点被二次访问，从而导致距离更新出错，通常使用初始化距离来标记是否被更新d != -1
二进制枚举
对于长度为n的序列，枚举每一位的组合，可以采用二进制枚举
注意若每一位都可以不出现则从0开始枚举，若至少出现一位则从1开始枚举
for (int i = 0; i < 1 << n; i++) { // 枚举所有可能的二进制数
for (int j = 0; j < n; j++) { // 枚举所有的二进制位
if ((i >> j & 1) == 1) { // 判断第j位是否为1
}
}
}
