跳转至

深度优先搜索（DFS）

1.关于搜索

​ 严格来说，搜索算法也是一种暴力枚举策略，但是其算法特性决定了效率比直接枚举所有答案要高，因为搜索可以跳过一些无效状态，降低问题规模。有些题目，无法用简单的循环表示所有枚举情况，需要寻找更加一般化的枚举框架；有些题目，本质上是子集枚举或是排列枚举，但是枚举量过大，需要剪掉过多的无效状态—深度优先搜索应运而生。

2.什么是深度优先搜索？

​ DFS 全称 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法.沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

​ 如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。简单来说就是一条路走到黑，直到没路了，或者找到结果才返回。

​ 深度优先搜索算法的基础：递归与回溯

递归与回溯是相辅相成的，有递归就会有回溯，递归函数的下面部分就是回溯的过程以及回溯的逻辑（即递归是回溯的基础）

3.如何理解

​ 回溯算法可以抽象为一个树状结构，可以抽象为一个n叉树问题。如果满足递归条件，则继续搜索，直到满足题目要求。如果走到尽头还未满足则回溯。

伪代码如下：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void 函数名（具体参数）{

​       if（终止条件）{

​           更新结果

​           return；

​       }

​       for（集合元素）{

​           处理节点

​           递归函数

​           回溯操作（撤销之前的操作）

​       }

​   return；

​}
图例如下：

​ 2.png

​ 3.png

​ 我们若以1为出发点开始遍历，那么我们其中一条搜索的遍历顺序则为1->2->4->7->4->8->4->2->1,遍历过程中我们要做的就是不断地向下向深处去搜索，秉承着不撞南墙不回头的思想，一直遍历到最下方，直到无法遍历，那我们向上回溯到它的父亲节点，向它的另一个子节点继续搜索。不断重复上述操作。

​ 我们从1号点出发选择左节点，紧接着向下搜索到达4号点，4号点同样有两种选择，先搜索左节点到达7号点，发现无路可走，向上回溯到达4号点，搜索右节点到达8号点后发现同样无路可走，接着向上回溯到达4号点，再次向上回溯到达2号点再到1号点。紧接着搜索1号点的右节点，将所有点搜素完毕后，以1号点为出发点的一次遍历才算结束。

栈实现

​ DFS 可以使用 栈（Stack） 为遍历中节点的暂存容器来实现；这与用 队列（Queue） 实现的 BFS 形成高度对应。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历
void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;
  while (!st.empty()) {
    int u = st.top();
    st.pop();
    for (int v : adj[u]) {
      if (!vis[v]) {
        vis[v] = true;  // 确保栈里没有重复元素
        st.push(v);
      }
    }
  }
}

4.例题解析

​ 一道经典例题：LuoguP1605 迷宫（普及-）（给大家直接抓取了，大家也可以去洛谷自行查看）

题目链接：https://www.luogu.com.cn/problem/P1605

题目描述

给定一个 \(N \times M\) 方格的迷宫，迷宫里有 \(T\) 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 \(N,M,T\)，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 \(SX,SY,FX,FY\)，\(SX,SY\) 代表起点坐标，\(FX,FY\) 代表终点坐标。

接下来 \(T\) 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1
1
2
3
2 2 1
1 1 2 2
1 2
样例输出 #1
1
1

提示

对于 \(100\%\) 的数据，\(1 \le N,M \le 5\)，\(1 \le T \le 10\)，\(1 \le SX,FX \le n\)，\(1 \le SY,FY \le m\)。

这是洛谷上一道基础的dfs入门题，可以通过这道题来了解一下dfs，练练手。

AC码如下：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
int a[11][11],l,r;
int dx[4]= {0,0,1,-1};
int dy[4]= {-1,1,0,0};//上加下减，左减右加
int n,m,t,sum=0,q,p;
void dfs(int x,int y) {
   if(x==q&&y==p) {
       sum++;//终止条件，可以套用模板，但是sum得设置为全局变量
   } else {
       for(int i=0; i<=3; i++) {                         
           if(a[x+dx[i]][y+dy[i]]==0&&y+dy[i]>0&&x+dx[i]>0) {
               a[x][y]=1;//代表（x,y)已经走过了
           //  printf("  %d %d\n",q,p);//验证数据是否正确
               dfs(x+dx[i],y+dy[i]);//回溯，递归
               a[x][y]=0;//保证循环中数据不变
           }
       }
   }
}
int main() {
   int x,y;
   scanf("%d %d %d",&n,&m,&t);
   scanf("%d %d %d %d",&x,&y,&q,&p);
   for(int i=1; i<=t; i++) {
       scanf("%d %d",&l,&r);
       a[l][r]=1; //这里是障碍点，可以理解为不能走，可以设置为已经走过的，赋值为1
   }
   for(int i=1; i<=n; i++)//墙壁   因为定义的数组大小是11*11的，如果不设置墙壁，就无法得到题目中说的n*m的矩形，所以要设置墙壁规定大小
       a[i][m+1]=1;
   for(int j=1; j<=m; j++)
       a[n+1][j]=1;
   dfs(x,y);
   printf("%d",sum);
   return 0;
}

dfs的整体思路还是比较容易想的，大家在写的过程中只需要将判断条件以及边界处理好即可

5.精选好题推荐（难度升序排列）

1.洛谷P1451 求细胞数量（普及-）

2.洛谷P10483 小猫爬山（普及-）

3.P1219 [USACO1.5] 八皇后 Checker Challenge（普及/提高-）

4.P2052 [NOI2011] 道路修建（普及/提高-）

5.P3956 [NOIP2017 普及组] 棋盘（普及+/提高）

6.P3659 [USACO17FEB] Why Did the Cow Cross the Road I G（提高+/省选）

PS：再高难度的题的话就不只是针对于dfs来考的了，所以这里不再给出，当然感兴趣同学可以自己上洛谷或者acwing查看

by LosTcrab