搜索（DFS/BFS）
发布时间 2023-07-20 20:43:07作者: MoiLip
广度优先搜索（BFS）
-
基本要点：
- 利用队列（先进先出）
- 一层一层搜索
- 适合于连通块的搜索
- 任何的BFS都可以转化为对树的广搜
-
基本流程：
- 选择搜索的起点，起点入队，起点标记为已访问
- 队列非空时，循环出队，每次出队将与出队元素连通的且未访问过的元素依次入队，并标记为已访问
-
基础模板：
void DFS(int x,int y){
q.push(start);
vis[start] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
for(所有与x联通的y){
if(vis[y] == 0){
q.push(y); vis[y] = 1;
}
}
}
}
-
题型归纳：
- [[Luogu P1451 求细胞数量]]
- [[Luogu P1162 填涂颜色]]
- [[Luogu P1443 马的遍历]]
- [[Luogu P3958 奶酪]]
- 题型总结：邻接条件一般是：1.增量数组（上下左右） 2.邻接矩阵（是否有边相连）
深度优先搜索（DFS）
-
基本要点：
- 通常用于解决最大/最长路径或者穷举所有可能的问题
- 用递归来实现
- 一条路走到黑
- 任何的DFS都可以转化为对树的深搜
-
基本流程：
- 选择一个起点进入DFS搜索
- 对于当前阶段/节点有多种处理决策，选择第一个决策，然后DFS下一个阶段
- 当第一个决策执行完毕后回溯，执行下一个决策
-
-
基础模板：
//非回溯版
void DFS(int x,int y){
cnt++;//用于记录遍历的节点数的变量
vis[x][y] = 1;//在DFS内部标记已访问不用回溯
for(int i = 1; i < 4; ++ i){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0)
DFS(nx,ny);
}
}
//回溯版
void DFS(int x,int y){
cnt++;//用于记录遍历的节点数的变量
for(int i = 1; i < 4; ++ i){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0){
vis[nx][ny] = 1;
DFS(nx,ny);
vis[nx][ny] = 0;//在DFS外部标记已访问要回溯
}
}
}
-
题型归纳：
- [[Luogu B3625 迷宫寻路]]
- [[Luogu P1706 全排列问题]]
- [[Luogu P4017 最大食物链计数]]
- [[Luogu P1219 八皇后]]
-
搜索剪枝优化：
- 记忆化搜索:
- 基本要点：
- 添加一个记忆化数组，对访问过的元素标记，避免重复访问
- 一般在递归函数中使用，当当前元素已经访问过时，直接返回值，跳过对该元素的处理
- 多用于动态规划的过程
- 基础模板：
int g[MAXN]; // 定义记忆化数组
int ans = 最坏情况, now;
void dfs f(传入数值) {
if (g[规模] != 无效数值) return; // 或记录解，视情况而定
if (到达目的地) ans = 从当前解与已有解中选最优; // 输出解，视情况而定
for (遍历所有可能性)
if (可行) {
进行操作;
dfs(缩小规模);
撤回操作;
}
}
int main() {
// ...
memset(g, 无效数值, sizeof(g)); // 初始化记忆化数组
// ...
}
- 题型归纳:
[[Luogu P4017 最大食物链计数]]
- 最优性剪枝：
- 可行性剪枝：