深度优先搜索（DFS）与广度优先搜索（BFS）详解

原文来自《挑战程序设计竞赛》

深度优先搜索（DFS）和宽度优先搜索（BFS）都是常见的搜索算法。在学习DFS和BFS之前，我们首先得知道递归函数的概念。

1. 递归函数

$$n!=n\times (n-1)!$$

规定$0!=1$，便可以很容易地编写出如下函数：

int f(int n) { 
    if (n == 0) { 
    return 1; } return n * f(n-1); } 

递归函数必须要有循环退出的条件，在这段代码中，$n==0$就是循环退出的条件。如果没有循环退出的条件，那么函数就会无限地调用下去，导致程序崩溃。
下面是计算阶乘的递归过程：

类似地，我们可以试着编写计算斐波那契数列的某一项的递归函数。斐波那契数列的定义如下：

设数列 { a n } , \{a_n\}, {
an​},若满足$a_0=0$,$a_1=1$,$a_n=a_{n-1}+a_{n-2}(n\ge 2)$,则称数列 { a n } \{a_n\} {
an​}为斐波那契数列

根据定义，我们知道斐波那契数列的递推式为$a_n=a_{n-1}+a_{n-2}$，循环退出的条件为$n=0$或$n=1$，这样就可以很容易地写出该递归函数：

int fib(int n) { 
    if (n <= 1) { 
    return n; } return fib(n-1) + fib(n-2); } 

我们在使用这个函数时，即使是求$n=40$这样$n$较小的情况的时候，也需要花费很长的时间。这是因为该递归函数在进行递归时，一次递归同时调用了两次自身，这样时间上就会随着$n$的增大指数级增加，如当$n=5$时：

可以看到有很多重复、不必要的调用，如fib(2)在程序中被调用了3次，这就浪费了时间，因此我们可以使用一个数组来将每一次计算得到的数存储起来，如果这一项被计算过了，直接返回数组对应的元素即可：

#include  
     using namespace std; #define max_N 10005 int arr[max_N]; int fib(int n) { 
    if (n <= 1) { 
    return n; } if (arr[n] != 0) { 
    return arr[n]; } return arr[n] = fib(n-1) + fib(n-2); } int main () { 
    int n; cin >> n; int res = fib(n); cout << res; } 

2. 深度优先搜索

部分和问题：
给定整数$a_1$,$a_2$,$\dots$,$a_n$，判断是否可以从中选出若干数，使得它们的和恰好等于$k$。
第一行输入一个整数$n$，表示有几个数据
第二行输入$n$个整数，表示$a_i$
第三行输入一个整数，表示$k$
限制条件：
*$1\le n\le 20$
*$-10^8\le a_i\le 10^8$
*$-10^8\le k\le 10^8$

样例输入1：
4
1 2 4 7
13
样例输出2：
Yes

样例输入2：
4
1 2 4 7
15
样例输出：
No

分析：
按照DFS的思想，我们可以把$a_1$作为搜索树的根节点，左子树为$a_1$被选用的情况，右子树为$a_1$不被选用的情况，用一个变量sum来计算被选择数据的和。

#include  
     using namespace std; #define max_N  int a[max_N]; int n, k; bool dfs (int i, int sum) { 
    //循环退出的条件，当i==n时，只需要判断sum是否与k相等即可  if (i == n) { 
    return sum == k; } //左子树，a[i]被选用的情况  if (dfs(i + 1, sum + a[i])) { 
    return true; } //右子树，a[i]不被选用的情况  if (dfs(i + 1, sum)) { 
    return true; } //不管选不选用a[i]，都凑不成k，则返回false  return false; } int main () { 
    cin >> n; for (int i = 0; i < n; i++) { 
    cin >> a[i]; } cin >> k; if (dfs(0,0)) { 
    cout << "Yes"; } else { 
    cout << "No"; } return 0; } 

接着我们来提高一下难度：

Lakee Counting（POJ NO.2386）:
有一个大小为$N\times M$的园子，雨后积起了水，八连通的积水被认为是连接在一起的，请求出园子里共有多少个水洼。（八连通指的是下图中相对$w$的$\ast$的部分）
$\ast \ast \ast$
$\ast w\ast$
$\ast \ast \ast$
第一行输入一个整数$N$
第二行输入一个整数$M$
接下来的$N$行$M$列表示园子的范围，其中“$w$”为积水
限制条件:
*$N,M\le 100$

样例输入：
$w\dots \dots ..ww.$
$.www\dots ..www$
$\dots .ww\dots ww.$
$\dots \dots \dots ww.$
$\dots \dots \dots w..$
$..w\dots \dots w..$
$.w.w\dots ..ww.$
$w.w.w\dots ..w.$
$.w.w\dots \dots w.$
$..w\dots \dots .w.$
样例输出：
3

分析:
可以从任意一个$w$的位置入手，将这个位置用”.”代替，并搜索它所对应八连通的位置，如果搜索的位置在园子内，并且值为$w$，则递归调用自身，重复上述步骤；直到某个点的八连通位置内没有$w$时退出循环。
依次对园子内的每个点进行如上操作，则dfs被调用的次数即为水洼的个数。

#include  
     using namespace std; #define max_N 105 int N,M; char field[max_N][max_N];//园子  void dfs (int x, int y) { 
    //将该位置用"."替换 field[x][y] = '.'; //循环遍历八连通的各个点 for (int dx = -1; dx <= 1; dx++) { 
    for (int dy = -1; dy <= 1; dy++) { 
    int nx = x + dx, ny = y + dy; //判断该点是否在园子内并且是否为积水 if (nx >= 0 && nx <= N && ny >= 0 && ny <= M && field[nx][ny] == 'w') { 
    dfs(nx, ny); } } } return ; } void solve () { 
    int res = 0; for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
    if (field[i][j] == 'w') { 
    dfs(i, j); res++; } } } cout << res; } int main () { 
    cin >> N >> M; for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
    cin >> field[i][j]; } } solve(); return 0; } 

3. 宽度优先优先搜索

迷宫的最短路径:
给定一个大小为$N\times M$的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。
第一行输入一个整数$N$
第二行输入一个整数$M$
接下来的$N$行$M$列为迷宫矩阵，“#”表示墙壁，“.”表示通道，“S”表示起点，“G”表示终点
限制条件:
$N,M\le 100$

样例输入：
10
10
$\#S.\#$
$\dots \dots \#..\#$
.$\#\dots \#$
$.\#\dots \dots ..$
$..\#$
$\dots .\#\dots .\#$
$.\#.\#$
$\dots .\#\dots ..$
$.\#..$
$\dots .\#\dots G\#$
样例输出：
22

宽度优先搜索按照距开始状态由近及远的顺序进行搜索，因此可以很容易地用来求最短路径、最少操作之类的问题的答案。这个问题中，状态仅仅是目前所在位置的坐标。因此可以构造pair或者编码成int来来表达状态。当状态更加复杂时，就需要封装成一个类来表示状态了。转移的方式为四方向移动，状态数与迷宫的大小是相等的，所以复杂度为$O(4\times N\times M)=O(N\times M)$。
只要将已经访问过的状态用标记管理起来，就可以很好地做到由近及远的搜索，这个问题要求最短距离，不妨用数组$d[N][N]$来把最短距离保存起来，初始时用一个充分大的常数$INF$来进行初始化，这样就保证了尚未到达的位置的值是$INF$，也就起到了标记的作用。
虽然到达终点时会停止搜索，可如果继续下去直到队列为空的话，就可以计算出各个位置的最短距离。此外，如果搜索到最后，$d$仍然为$INF$的话，这个位置就是无法从起点到达的。
用$dx[4]$和$dy[4]$两个数组来表示四个方向向量。这样通过一个循环可以实现方向的移动。

#include  
     using namespace std; #define max_N 20 const int INF = ; char maze[max_N][max_N + 1]; int N, M; int sx, sy; //起点  int px, py; //终点  int d[max_N][max_N]; //4个方向移动的分量 int dx[4] = { 
   1, 0, -1, 0}; int dy[4] = { 
   0, 1, 0, -1}; //使用pair表示状态时，使用typedef会更加方便一些  typedef pair<int, int> P; int bfs () { 
    queue<P> que; //初始化 for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
    d[i][j] = INF; if (maze[i][j] == 'S') { 
    sx = i; sy = j; } if (maze[i][j] == 'G') { 
    px = i; py = j; } } } //起点加入队列 que.push(P(sx, sy)); d[sx][sy] = 0; //不断循环直到队列长度为0 while (que.size()) { 
    //从队列中取出第一个元素 P p = que.front(); que.pop(); //如果这个点是终点，则结束搜索 if (p.first == px && p.second == py) { 
    break; } //四个方向的循环 for (int i = 0; i < 4; i++) { 
    int nx = p.first + dx[i]; int ny = p.second + dy[i]; //判断是否可以移动，以及是否已经被放问过 if (nx > 0 && nx < N && ny > 0 && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) { 
    //如果可以移动，则讲该点加入到队列，并将起点到该点的距离确定为到p的距离+1 que.push(P(nx, ny)); d[nx][ny] = d[p.first][p.second] + 1; } } } return d[px][py]; } int main () { 
    cin >> N >> M; for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
    cin >> maze[i][j]; } } int res = bfs(); cout << res; return 0; } 

这是博主写的第一篇博客，如有不明确的地方或者不懂的地方，欢迎在下方留言交流，博主也会继续分享算法知识