DFS和BFS¶
一、配套视频¶
https://www.bilibili.com/video/BV1RD4y1F7Fq
二、DFS（深度优先搜索）¶
2.1问题引出¶
我们想知道在一个迷宫里面是否有一个路线能让我们从起点走到终点，无论改路径是否是最优的
例题：http://acm.mangata.ltd/p/E427
2.2思路¶
由于我们只想知道这个迷宫有没有解，所以我们期望能够一条路就走到终点，然后保存这个信息，但是这个过程中我们很可能就走到了一个死路，正常的思维会怎么想呢？退回来，一只退回到有没走过的岔路口，然后走向另一个方向，然后重复这个过程直到找到了终点，或者说所有的点都走过了，那么我们就退出，这就是深度优先的思想。
2.3重点¶
重点理解一下这个递归的过程，递的过程其实就是往下一个地方走，归的过程就是走到死胡同了，我们要返回到岔路口。这里归的过程也就是回溯，回溯的状态是非常关键的，有的时候我们要利用回溯这个过程记录一些信息，比如路径、权值和等，所以DFS不仅能运用到路径的搜索，在很多地方都能用到
2.4实现的方式¶
实现的方式也就是通过递归实现，不断向下探索，然后遇到死胡同就归上来
给出一个模板：
void dfs(int x,int y){//x、y表示的是坐标点的位置
if(vis[x][y]) return;//这个表示已经访问过了
vis[x][y] = true;//如果没有访问过，那么我们现在访问过了
ans++;
for(int i = 0;i < 4; ++i) {//这里就是往上下左右四个方向遍历
int nx = x + dx[i];
int ny = y + dy[i];
if(!vis[nx][ny] && nx > 0 && nx <= H && ny > 0 && ny <= W && mp[nx][ny] != '#') {//我们这里就是看下一个位置是否能递归访问
dfs(nx,ny);
}
}
}
三、BFS（广度优先搜索）¶
3.1问题引出¶
我们想知道在一个迷宫里面是否有一个路线能让我们从起点走到终点，并且路线是最优的，然后输出最优路径的长度
例题：http://acm.mangata.ltd/p/E427
3.2思路¶
由于我们现在的这个问题转变为了最优路径求解，所以我们经量就不要使用DFS（因为递归的过程很耗时间），这个时候就需要BFS（广度优先搜索），什么意思呢，我们尽可能地找到靠近我们当前这个点的周围的点。然后将这个周围的点加入我们即将探寻的这个队列里面。这个过程大概就是一层一层的去访问这些可行的点，这也就是广度优先搜索。
1.我们先将起点放进队列，然后逐步去找起点周围的点，然后将这个周围的点也放进队列，然后将起点移出队首。
2.我们再取出当前队首的点，然后重复上面的过程，直到取出的点是终点。
3.3重点¶
重点就是这个入队的过程的理解，你要知道广度优先搜索的工作方式是优先将靠近当前点的周围的点放进队列，然后逐步去访问操作，在后续的过程中我们可以根据这个思维去优化SPFA算法以及优化。
3.4实现方式¶
实现方式也就是队列的应用，主要理解的这个思路是广度优先
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int bfs(int sx,int sy){
int cnt = 0;
q.push(node{sx,sy,0});//压入队列
while(!q.empty()){//队列不为空
node p=q.top();//取出队列第一个元素
q.pop();//弹出
if(p.x == ex,p.y == ey){//找到终点然后直接返回路径的长度
return p.k;
}
if(vis[p.x][p.y]) continue;//已去过就不去了
vis[p.x][p.y] = true;//标记已去过
for(int i=0;i < 4;++i){
int nx = x + dx[i];
int ny = y + dy[i];
if(check(nx,ny)){
que.push(node{nx,ny,p.k+1});
}
}
}
return -1;//没有路径的
}
四、总结两种方式¶
4.1维护方式¶
DFS用递归的形式，用到了栈结构，先进后出。
BFS选取状态用队列的形式，先进先出。
4.2复杂度¶
DFS的复杂度与BFS的复杂度大体一致，不同之处在于遍历的方式与对于问题的解决出发点不同，DFS适合目标明确，而BFS适合大范围的寻找。
4.3思想¶
思想上来说这两种方法都是穷竭列举所有的情况。但是不同的是，DFS可以通过剪枝等操作优化，而BFS必须穷举出所有情况