深度优先搜索

5.1. 从递归到深度优先搜索
深度优先搜索，简称 dfs，是一个经典的搜索算法，能够把具体的方案找出来。现在我们要把 dfs 和递
归联系起来。前面学习递归的时候，我们学习过用递归实现阶乘

int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n ‐ 1);
}

和用递归实现斐波那契数列

	int fib(int n) {
	if (n == 1 || n == 2) {
	return 1;
	}
	return fib(n ‐ 1) + fib(n ‐ 2);
	}

实际上前面的两个都方法可以称为深度优先搜索，也就是说在前面的学习过程中，我们已经在无形之
中使用了深度优先搜索。
深度优先搜索按照深度优先的方式进行搜索，通俗点说就是“一条路走到黑”。注意，这里的“搜索”不是
指的我们平时在文件中或者在网络上查找某些信息，搜索是一种穷举的方式，把所有可行的方案都列
出来，不断去尝试，直到找到问题的解。
深度优先搜索和递归的区别是：深度优先搜索是一种算法，注重的是思想；而递归是一种基于编程语
言的实现方式。深度优先搜索可以用递归实现，也就是说递归是我们用计算机编程语言来实现深度优
先搜索这个算法的手段。
ps：当然，我们也同样可以用非递归的方式实现搜索，大家在之后的课程里就会明白啦。

上图是Fib（5） 的搜索过程，我们发现这个过程实际上对应着一棵树，这颗树被称为 搜索树。在这
里，我们先不必理解搜索树，等我们对深度优先搜索算法有了一定的了解以后，再去深入探讨它。
5.2. 再探迷宫游戏
接下来，我们通过一个实际问题 ­­《迷宫游戏》来学习 dfs（在后面的课程中，我们都会用 dfs 来替代
深度优先搜索）。
我们用一个二维的字符数组来表示前面画出的迷宫：
S**.
…
***T
其中字符 S 表示起点，字符 T 表示终点，字符 * 表示墙壁，字符 . 表示平地。你需要从 S 出发走
到 T ，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一
次。你需要编程来求解出一种从起点到终点的走法。
迷宫问题的解法就需要用到 dfs。我们对上下左右四个方向，一个方向一个方向地尝试，如果沿着某个
方向不能走到终点，我们就要原路返回，继续尝试其他方向，直到走出迷宫。这是一种最朴素的走迷
宫方式，虽然效率也许比较低，但如果迷宫有解，就一定能走出终点。

上面说的这种走法，就对应着我们要讲的 dfs 算法。首先找到起点 S ，走到每个点时，按照左、下、
右、上的顺序尝试。每走到下一个点以后，我们把这个点当做起点 S ，继续按顺序尝试。如果某个点
上下左右四个方向都尝试过，便回到走到这个点之前的点，这一步我们称之为 回溯。继续尝试其他方
向。直到所有点都尝试过上下左右四个方向。
这就好比你自己去走这个迷宫，你也要一个方向一个方向的尝试着走，如果这条路不行，就回头，尝
试下一条路，dfs 的思想和我们直观的想法很类似。只不过，接下来我们需要用程序来完成这个过程。
dfs 走迷宫对应的代码框架如下：

// 对坐标为 (x, y) 的点进行搜索
bool dfs(int x, int y) {
if (x, y) 是终点 {
// 找到了路径
return true;
}
标记 (x, y) 已经访问
向上走到位置 (tx, ty)
if (tx, ty) 在地图里面且没有访问 {
if (dfs(tx, ty) == true) {
return true;
}
}
向左走到位置 (tx, ty)
if (tx, ty) 在地图里面且没有访问 {
if (dfs(tx, ty) == true) {
return true;
}
}
向下走到位置 (tx, ty)
if (tx, ty) 在地图里面且没有访问 {
if (dfs(tx, ty) == true) {
return true;
}
}
向右走到位置 (tx, ty)
if (tx, ty) 在地图里面且没有访问 {
if (dfs(tx, ty) == true) {
return true;
}
}
取消 (x, y) 访问标记
return false;
}

【实践操作】迷宫搜索实践1
这一节课我们通过实践解决迷宫游戏。初始化代码已经为你写好了输入。这里我们用 string 来储存迷
宫地图。
接下里根据前面阅读里面的代码框架来实现搜索。

在 main 函数上面写下

bool dfs(int x, int y) {
}

其中传入两个参数 来表示一个位置， 代表行， 代表列。
我们首先处理好边界条件，什么时候搜索结束？如果搜索到了终点，自然就要结束搜索，边界条件就
是 maze[x][y] == ‘T’ 。
另外为了防止走回头路，我们还需要标记一下当前这个点已经走过了。所以需要用一个 vis 数组来做
标记。同时为了标记出来路径，我们把走过的点用字符 ‘m’ 标记。
在 dfs 函数里面写下

if (maze[x][y] == 'T') {
return true;
}
vis[x][y] = 1;
maze[x][y] = 'm';

vis 使用了但是还没有定义哦，我们把 vis 定义成全局变量，在 dfs 函数的上
面， string maze[110]; 下面写下

bool vis[110][110];

边界处理好了以后，就要开始真正的搜索了。我们的人的位置现在 ，如果往上面走，就走到了
，如果 不是 ‘*’ ，并且还没有访问，我们就可以继续在 的位置进行
搜索，如果从这个位置能搜到解，那么可以直接返回 true 。
注意，为了防止搜索到地图外面，我们需要判断一下是否在地图里面，而这个判断我们一般用一个函
数 bool in(int x, int y) 来判断，这一步我们假设这个函数已经实现，先调用
在 dfs 函数里面继续写

int tx = x ‐ 1, ty = y;
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
if (dfs(tx, ty)) {
return true;
}
}

接着我们尝试向左搜索到达 ，逻辑和向上一模一样。
继续在 dfs 里面写下

tx = x, ty = y ‐ 1;
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
if (dfs(tx, ty)) {
return true;
}
}

同理，我们继续写向下和向右边的搜索。
接着刚才的继续写下

tx = x + 1, ty = y;
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
if (dfs(tx, ty)) {
return true;
}
}
tx = x, ty = y + 1;
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
if (dfs(tx, ty)) {
return true;
}
}

不要以为写到这里搜索函数已经写完了，记住还有最重要的一步——回溯，如果我们四个反向都搜完
了，也没有找到路径，那么函数运行结束，返回到上一层的递归，在函数返回之前，我们必须要做一
些处理，把刚才我们访问这个位置的时候做的标记全部都要撤销，还原之前的状态。
在 dfs 末尾写下

	vis[x][y] = 0;
	maze[x][y] = '.';
	return false;

这一步，我们补充山刚才还没有实现的 in 函数，实际上 in 的实现很简单。
在 dfs 函数定义的上面， bool vis[110][110] 下面的位置写下

bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}

该验证我们写了这么久的 dfs 函数了。在调用 dfs 函数之前，我们得先找到迷宫的起点，这个很简
单。在 main 函数的输入下面写下

int x, y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
x = i, y = j;
}
}
}

终于到最后一步了，剩下的只需要调用 dfs 函数了，如果找到了路径，输出这条路径。
在 main 函数里面继续写下

if (dfs(x, y)) {
for (int i = 0; i < n; i++) {
cout << maze[i] << endl;
}
} else {
cout << "NO!" << endl;
}

终于完成了，到这一步一定不容易，点击运行，输入下面的数据，你一定会很惊喜地看到自己的成
果。
5 6
…S*
.*…
.….
.**.
.T…
【实践操作】迷宫搜索实践2

#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
int x, y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
x = i, y = j;
}
}
}
if (dfs(x, y)) {
for (int i = 0; i < n; i++) {
cout << maze[i] << endl;
}
} else {
cout << "NO!" << endl;
}
return 0;
}

上一节课我们已经实现了搜索，代码很长，写起来一定很累。实际上我们可以通过一个巧妙的方法来
较少代码量。
我们在下一步介绍这个方法，这一步先把边界写上，和上一节课程一样，
在 dfs 函数里面写下

if (maze[x][y] == 'T') {
return true;
}
vis[x][y] = 1;
maze[x][y] = 'm';

仔细观察和对比四个方向的搜索。

除了 不一样以外，其他的部分都是完全一样的。
我们想办法把四个方向写到一块，定义一个方向变量（我们习惯把全局变量都定义到一块代码区
域），
在 bool vis[110][110]; 下面，在 in 函数上面写下

int dir[4][2] = {{‐1, 0},{0, ‐1},{1, 0},{0, 1}};

然后在 dfs 函数里面写下下面的代码

for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
if (dfs(tx, ty)) {
return true;
}
}
}

通过巧妙的构建方向变量，这样就可以通过 for 循环枚举方向了。
这一步写下回溯的代码。

vis[x][y] = 0;
maze[x][y] = '.';
return false;

终于完成了，到这一步一定不容易，点击运行，输入下面的数据，你一定会很惊喜地看到自己的成
果。
5 6
…S*
.*…
.….
.**.
.T…
【例题1】中国象棋
中国象棋博大精深，其中马的规则最为复杂，也是最难操控的一颗棋子。
我们都知道象棋中马走"日"，比如在 位置的一个马，跳一步能到达的位置有 ， ，
， ， ， ， ， 。
(2, 4) (0, 3) (0, 5)
(1, 2) (1, 6) (3, 2) (3, 6) (4, 3) (4, 5)

蒜头君正在和花椰妹下棋，蒜头君正在进行战略布局，他需要把在 位置的马跳到 位
置，以达到威慑的目的。
但是棋盘大小有限制，棋盘是一个 的网格，左上角坐标为 ，右下角坐标为 ，马不
能走出棋盘，并且有些地方已经有了棋子，马也不能跳到有棋子的点。
蒜头君想知道，在不移动其他棋子的情况下，能否完成他的战略目标。
输入格式
输入一共 行，每行一个长度为 的字符串。
输入表示这个棋盘，我们用 ‘.’ 表示空位置，用 ‘#’ 表示该位置有棋子，用 ‘S’ 表示初始的马的位
置，用 ‘T’ 表示马需要跳到的位置。
输入保证一定只存在一个 ‘S’ 和一个 ‘T’ 。
输出格式
如果在不移动其他棋子的情况下，马能从 ‘S’ 跳到 ‘T’ ，那么输出一行 “Yes” ，否则输出一行 “No” 。
样例输入
.#…#S#
…#.#.#…
…##.#…#
…##.
…T…
…#.#…
…#…
…###…
…
.##…

样例输出
Yes

5.3. 图和搜索
深度优先搜索实际上本质是一种图算法，也就是说任何的搜索都是在图上完成的。比如前面的迷宫问
题本质就是图。
下图是一个无向图，如果我们从 A点开始深度优先搜索（以下的访问次序并不是唯一的，第二个点既
可以是B 也可以是 C、D ），则我们可能得到如下的一个访问过程：A ­> B­> E，回溯到A ，继续
访问C ­>F ­> ­H>G ­> D，回溯到 A， A此时已经没有未访问的相邻顶点，本次搜索结束。最终
通过 ­A> ­B>E ­> ­C>F ­> H­>G ­>D 的顺序搜索了图中的所有顶点。

深度优先搜索的本质可以借助栈来理解。实际上，当访问一个点的时候，相当于把这个点入栈。而从
一个点回溯的时候，相当于弹出栈顶元素。栈顶元素总是当前正在访问的点。后面的演示课我们将会
更直观地看到这一点。
对于无向图来说，我们定义图 上的极大连通子图 为：
是 的子图，且 是连通的
如果 也是 的连通子图，且 是 的子图，一定
我们通常把极大连通子图简称为 连通块。
在无向图上，利用 dfs 可以求连通块的数量。算法流程如下：

1. 选择一个尚未被访问的点 ，从点 出发进行深度优先搜索，对访问过的点进行标记

2. 继续寻找下一个尚未被访问的点，直到没有尚未被访问的点，算法结束
   进行深度优先搜索的次数就是图中的连通块个数，如果我们在每次进行深度优先搜索时，对访问过的
   点进行不同的标记，就可以记录每个连通块内的顶点有哪些了。
   【小练习】联通块数量
   
   上面的无向图有多少个个连通块？
   【实践操作】图的遍历
   这一节我们来实现一个在无向连通的图上的搜索。
   不知道大家是否还记得图的储存，为了帮大家回忆图的存储，这一节我们用邻接表来存图。
   在第一步我们输入一张图，用邻接表储存起来。
   首先我们需要定义一个储存图的 vector ，在 using namespace std; 之后写下：
   vector G[110];
   然后在 main 函数里面写下

   int n, m;
   cin >> n >> m;
   for (int i = 0; i < m; i++) {
   int a, b;
   cin >> a >> b;
   G[a].push_back(b);
   G[b].push_back(a);
   }
   现在我们从某个点开始对图进行 dfs，在 main 函数上面写下
   bool vis[110];
   void dfs(int x) {
   }
   vis 是用来标记每个店是否访问过的。
   现在正在访问顶点 x，我们需要标记 x 已经访问。

在 dfs 函数里面写下

vis[x] = 1;
cout << "Visiting " << x << endl;
然后我们去遍历和 相连的顶点，继续访问没有访问过的顶点。
在 dfs 函数里面继续写下
for (int i = 0; i < G[x].size(); i++) {
int v = G[x][i];
if (!vis[v]) {
dfs(v);
}
}

接下来是搜索的最后一步，回溯，本来这里应该取消标记，但是这里我们只是为了遍历这个图，所以
就不取消标记了。
你可能还有一个疑问，为什么没有判断边界条件呢？实际上，如果和某个点相邻的点都已经访问过
了，这个点就没办法继续搜索了，这个分支的搜索就结束了，所以不可能无限递归下去。
在这一步，我们只需要调用 dfs(1) 从 1 点开始遍历图。
在 main 函数里面输入下面写下
dfs(1);
这一节已经完成，点击运行，然后输入下面的数据：
5 6
1 2
1 3
2 4
2 5
3 5
4 5
【例题2】连通块数量
输入一个无向图，求图中连通块的个数。
输入格式
输入第一行两个整数 ，表示图的点的数量和边的数量。
接下来 行，每行两个整数 ，表示一条无向边。
x
n, m(1 ≤ n, m ≤ 20000)
m a, b(1 ≤ a, b ≤ n)

输出格式
输入一行一个整数，表示图中连通块的个数。
样例输入
5 4
2 3
4 1
5 2
2 2
样例输出
2
【实践操作】迷宫最短路

#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{‐1, 0},{0, ‐1},{1, 0},{0, 1}};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> maze[i];
}
int x, y;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') {
x = i, y = j;
}
}
}
return 0;
}

前面我们学习的迷宫上的搜索只是在寻找是否有路径可达，现在我们想求出最少需要多少步能到达终
点。

还是借助搜索，我们只需要在搜索的时候多记录一些其他信息，用一个参数来记录前面搜索已经走了
多少步了。
在 main 函数上面写下

void dfs(int x, int y, int step) {
}

这一步我们先完成搜索和回溯部分，稍后再处理边界，这部分和前面的写法没有太大的区别。
在 dfs 函数里面写下

vis[x][y] = 1;
for (int i = 0; i < 4; i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]) {
dfs(tx, ty, step + 1);
}
}
vis[x][y] = 0;

这一步我们来处理边界情况情况，到达边界情况说明找到了一条路径，而这条路径对应的需要的步数
为 step ，我们只需要定义一个全局变量 ans 来记录一个最小值，初始的时候， ans 要赋值成为一个很
大的数。
在 int dir[4][2] = {{‐1, 0},{0, ‐1},{1, 0},{0, 1}}; 下面写下
int ans = 100000000;
然后在 dfs 函数开头写下

if (maze[x][y] == 'T') {
if (step < ans) {
ans = step;
}
return;
}

最后我们对起点调用 dfs 函数，初始的时候，传入的 step 参数的值为 。最后最短的答案就记录
在 ans 中。
在 main 函数中写下

dfs(x, y, 0);
cout << ans << endl;

0

这一节已经完成了，点击运行，输入下面的数据。
5 6
…S*
.…
.….
*….
.T…