搜索
搜索
DFS · 深度优先搜索
定义
深度优先搜索属于图算法的一种，英文缩写为 DFS 即 Depth First Search. 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
——百度百科
在一条路上的分岔按顺序选择方向，一条路走到底再返回到最近分岔选择下一条路，这个分岔下所有路全走完后再返回到更上一个分岔走下一条路。
基本思路
深度优先遍历图的方法是，从图中某顶点v出发：
- 访问顶点 v ；
- 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
- 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
搜索完节点后注意是否需要回溯！
模板
bool judge(int x, int y) {}; //判断当前状态是否合法
bool check(int x, int y) {}; //判断是否为最终答案
void dfs(int x, int y, int z)
{
if(!judge(x, y)) return;
if(check(x, y))
{
//保存答案
}
vis[x][y] = 1; //标记已搜索过此节点，防止重复搜索
/*
操作...
*/
dfs(x - 1, y, z + 1);
dfs(x + 1, y, z + 1);
dfs(x, y - 1, z + 1);
dfs(x, y + 1, z + 1);
vis[x][y] = 0; //回溯
}优化
剪枝
有些求最优解的题目，可以不用完全遍历，当目前 dfs 的解已经比历史遍历得到的最优解更差时，可以停止遍历，节省一部分时间复杂度。
bool judge(int x, int y) {}; //判断当前状态是否合法
bool check(int x, int y) {}; //判断是否为最终答案
void dfs(int x, int y, int z)
{
if(!judge(x, y)) return;
if(z >= ans) return;
if(check(x, y))
{
ans = z;
//保存答案
}
vis[x][y] = 1; //标记已搜索过此节点，防止重复搜索
/*
操作...
*/
dfs(x - 1, y, z + 1);
dfs(x + 1, y, z + 1);
dfs(x, y - 1, z + 1);
dfs(x, y + 1, z + 1);
vis[x][y] = 0; //回溯
}记忆化搜索
对于遍历某些确定的类型时，如果到达一个节点之后的遍历结果是可以确定的，第一遍先向下遍历得到结果，将这个结果保存，之后再遍历到此节点时直接返回已得到的结果，可以节省一部分时间复杂度。
如：[洛谷 P1434 [SHOI2002]滑雪](https://www.luogu.com.cn/problem/P1434)
题目大意：矩阵求最长下降线路长度
int fx[5] = { 0, 0, 0, 1, -1 };
int fy[5] = { 0, 1, -1, 0, 0 };
int dfs(int x, int y)
{
if (f[x][y]) return f[x][y]; //记忆化搜索
f[x][y] = 1; //题目中答案是有包含这个点的
for (int i = 1; i <= 4; i++)
{
int xx = fx[i] + x;
int yy = fy[i] + y; //四个方向
if (xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy])
{
f[x][y] = max(f[x][y], dfs(xx, yy) + 1);
}
}
return f[x][y];
}BFS · 广度优先搜索
定义
从出发点一层一层向外遍历，到达终点就结束。因此，到达终点的方案一定是最优解。
无论有多少条路，每条路都只走一步，并记录下状态，等到所有的路都走完一步后，再从第一条路开始走第二步，直至有一条路走到终点。
基本思路
广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：
把根节点放到队列的末尾。
每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
- 找到所要找的元素时结束程序。
- 如果遍历整个树还没有找到，结束程序。
模板
int fx[5] = { 0, -1, 1, 0, 0 };
int fy[5] = { 0, 0, 0, -1, 1 }; //上下左右
struct node
{
int x, y, z;
};
bool check (int x, int y) {}; //判断点是否能走
void bfs(int x, int y, int z)
{
node start;
start.x = x;
start.y = y;
start.z = 0; //start 为出发点，z 为步数
queue <node> q;
q.push(start); //将出发点推入队列中等待处理
while (!q.empty())
{
node now;
now = q.front(); //从队列中取出首元素处理
q.pop(); //将该元素取出后要记得推出，否则只推入不推出，死循环
t[now.x][now.y] = now.z; //这里是记录了到 [now.x][now.y] 的最短路径，也可以做其他操作
for (int i = 1; i <= 4; i++) //往四个方向继续遍历
{
if (check (now.x + fx[i], now.y + fy[i]))
{
node next;
next.x = now.x + fx[i];
next.y = now.y + fy[i];
next.z = now.z + 1;
vi[next.x][next.y] = 1;
q.push(next); //将该点保存并推入队列中，等待前面的处理完后再走下一步
}
}
}
}