深度优先搜索——DFS

基本概念

深度优先搜索可以理解为”不撞南墙不回头“，会在一条路径上一直进行搜索，直到到达这条路径的终点后，才会回头去搜索其他可能的节点，下图展示了一个可能的深度优先搜索的顺序：

数字即搜索时访问的顺序，这里设定的搜索的方案是 ”如果左边还能走，就一直往左走，否则才往右走。“

整个搜索的过程有点像——入栈和出栈，可以发现，其顺序是后进先出的，所以你想的没错，DFS的实现正是基于栈的思想。

全排列问题

来看一个问题：

例题-排列数字

题目描述

给定一个整数 n(1≤n≤7)n(1 \leq n \leq 7)，将数字 1∼n1 \sim n 排成一排，将会有很多种排列方法。 现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 nn。

输出格式

按字典序输出所有排列方案，每个方案占一行。

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

题目分析

如果把 nn 固定为某个数字，比如 33，相信大家肯定会写，三层嵌套循环秒了。可是，现在 nn 是不确定的，那么循环的层数也是不确定的，如果用普通循环来实现会有些麻烦，那有没有办法可以让循环的层数可以改变呢？

答案就是 —— 递归！

假设 nn 是 33，来看看递归树是什么样子的：

image-20240313234358082.png

标的号是搜索的顺序。

要想实现这样的过程，需要通过哪些步骤呢？

  1. 其一，要往下搜索，即有一个往下递进的过程。
  2. 其二，要往上回溯，即有一个恢复现场的过程。

先看第一个步骤，往下递进要进行哪样的操作呢？无非就是 从 1∼n1 \sim n 中选一个没有使用的数字进去，然后递归调用到下一层，继续选，可以这样理解：

循环 1~n {
	判断当前数字是否使用过:  // 如何判断是否使用呢？很容易可以想到，用桶。
		没有使用，选择这个数字。
        标记这个数字已经使用。
        递归进入下一层。
}

再看第二个步骤，回溯就是当这次调用的递归函数运行完成后，重新回到这一层时，需要”恢复成调用之前的状态“。

之前的状态是什么样的？这个数字没有被选用，所以其实就是要取消这个数字的选用，即可。

那么代码流程就变成了：

循环 1~n:
	判断当前数字是否使用过:  // 如何判断是否使用呢？很容易可以想到，用桶。
		没有使用，选择这个数字。
        标记这个数字已经使用。
        递归进入下一层。
        标记这个数字未使用。
        取消这个数字的使用。

还剩最后一个问题，递归到什么时候结束呢？观察上面的图，我们都是走到什么地方才开始回头的？当选择了所有的数字后！所以递归的结束条件就是所有的数字都选择完！所以我们应该需要一个参数，来记录当前选择的数字的数量。

到此，递归函数的几个要素已经基本思考完成：

  1. 函数参数，需要一个变量 cnt 来记录当前选择的数字的数量。
  2. 边界条件，当 cnt 等于 n 时，表示所有数字都选了，此时终止递归函数。
  3. 如何进行递进，循环选择 1~n 中没有被选的数字，然后递进。
  4. 如何进行回溯，函数调用完成后，取消数字的使用，即可完成回溯。

示例代码

#include <bits/stdc++.h>
using namespace std;
int n, vis[15];
vector<int> path;

void dfs(int cnt) {
	if (cnt == n) {
		// 此时说明数字全部都选了，那么应该输出答案
		for (int i=0; i<n; i++) {
			cout << path[i] << ' ';
		} 
		cout << '\n';
		return ;
	}
	for (int i=1; i<=n; i++) {
		if (!vis[i]) {  // 判断数字是否使用过 
			vis[i] = 1;  // 标记数字i被使用 
			path.push_back(i);  // 加入使用的数组中 
			dfs(cnt+1);  // 继续往下搜索，并且使用的数字数量+1 
			path.pop_back();  // 已经搜索完了，将它弹出使用数组
			vis[i] = 0;  // 标记为未使用过 
		}
	}
}

int main() {
	cin >> n;
	dfs(0);
	return 0;
}

其实可以发现，这个搜索最终达到的结果，其实和枚举是很像的，都是按照某个顺序把所有可能的情况列出来，然后再根据题目的条件去进行筛选。比如，如果这一个题目加一个条件，所有选择的数字的和要刚好等于某个值，那怎么做？就在最后到达边界时加一个判断就可以了，就像在嵌套循环的最内层加一个判断一样。因此，DFS又常常被称之为暴搜，一般时间复杂度都很高，例如上面这段代码的时间复杂度介于 O(n!)O(n!) 和 O(n×n!)O(n \times n!) 之间。

DFS的代码结构基本类似，如下所示：

void dfs(参数) {
    if (到达边界) {
		进行答案处理
        return ;
    }
    往下递进  // 可能用循环，也可能题目的分支数是固定的，不用循环
    回溯状态  // 有些情况也不用回溯
}

不过，DFS的代码并没有固定的模板，上述也只是一个常见的格式罢了，在思考相关问题时，最重要的还是思考清楚搜索的顺序、中间的限制条件、边界条件等等。

排列组合问题拓展【课后思考】

一、可重复选用的排列问题

题目描述

给定一个正整数 nn，从 1∼n1 \sim n 中任选 nn 个数字（可以重复选用），排成一个数字，按字典序输出所有的排列方案。

输入格式

共一行，包含一个整数 nn。

输出格式

按字典序输出所有排列方案，每个方案占一行。

输入样例

2

输出样例

1 1
1 2
2 1
2 2

示例代码

int n;
vector<int> path;

void dfs(int cnt) {
	// cnt记录数字的数量 
	if (cnt == n) {  // 选够n个数字了 
		for (int i=0; i<n; i++) cout << path[i] << ' ';
		cout << '\n';
		return ;
	}
	for (int i=1; i<=n; i++) {
		// 因为可以重复选用，所以不用标记是否使用过 
		path.push_back(i);  // 选数字 
		dfs(cnt+1);  // 递进，注意参数范围 
		path.pop_back();
	} 
}

可以发现，和全排列问题的区别就是去掉了标记数组 vis ，时间复杂度为 O(n×n!)O(n \times n!)。

二、可重复选用的组合问题

题目描述

给定两个正整数 nn 和 kk，从 1∼n1 \sim n 中选择任意个数字（可以重复选用），使得数字的总和等于 kk，按字典序输出所有的选择方案。

输入格式

共一行，包含两个整数 n,kn,k。

输出格式

按字典序输出所有选择方案，每个方案占一行。

输入样例

3 5

输出样例

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

示例代码

int n, k;
vector<int> path;

void dfs(int sum, int last) {
	// last在这里起到的作用
	// 就是让本层的选择范围可以从上次选的数字开始，可以避免重复。 
	if (sum == k) {  // 和为k时就是一个答案了 
		for (int i=0; i<path.size(); i++) cout << path[i] << ' ';
		cout << '\n';
		return ;
	}
	if (sum > k) return ;  // 超过了，已经不可能是答案了
	for (int i=last; i<=n; i++) {
		path.push_back(i);  // 选数字 
		dfs(sum+i, i);  // 递进，注意参数范围 
		path.pop_back();
	} 
}

关键点在于每次选择数字时的范围，是 上次选的数字~n，这样做避免了枚举出重复的情况，例如枚举出 1 2 3 和 3 2 1，在这个范围下不会出现 3 2 1 ，时间复杂度为 O(n!)O(n!)。

三、不可重复选用的组合问题

题目描述

给定两个正整数 nn 和 kk，从 1∼n1 \sim n 中选择任意个数字（不可以重复选用），使得数字的总和等于 kk，按字典序输出所有的选择方案。

输入格式

共一行，包含两个整数 n,kn,k。

输出格式

按字典序输出所有选择方案，每个方案占一行。

输入样例

5 10

输出样例

1 2 3 4
1 4 5
2 3 5

示例代码

int n, k;
vector<int> path;

void dfs(int sum, int last) {
	// last在这里起到的作用
	// 就是让本层的选择范围可以从上次选的数字+1开始，可以避免重复。 
	if (sum == k) {  // 和为k时就是一个答案了 
		for (int i=0; i<path.size(); i++) cout << path[i] << ' ';
		cout << '\n';
		return ;
	}
	if (sum > k) return ;  // 超过了，已经不可能是答案了
	for (int i=last+1; i<=n; i++) {  // 注意范围，这里是last+1
		path.push_back(i);  // 选数字 
		dfs(sum+i, i);  // 递进，注意传参的值
		path.pop_back();  // 回溯
	} 
}

比起可重复的组合问题，只是范围变成了 上次选的数字+1~n ，时间复杂度为 O(n!)O(n!)。

八皇后问题

再来看一个经典问题：

八皇后问题

题目描述

n−n-皇后问题是指将 nn 个皇后放在 n×nn\times n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 nn，请你输出所有满足条件的棋子摆法。

输入格式

共一行，包含一个整数 nn。

输出格式

每个方案应该是一个 nn 行 nn 列的二维字符数组，其中 . 表示这个方格为空，Q 表示这个方格上摆着皇后。每输出完一个方案后，应该输出一个空行后再输出下一个方案。输出方案的顺序任意，只要不重复且没有遗漏即可。

样例输入

4

样例输出

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

第一种思路

比较容易想到一种方案，就是挨个去尝试每个格子放皇后或者不放皇后，然后最后再检查答案是否有效，可以画出其搜索树：

image-20240314134530914.png|600

大概流程：

void dfs() {
    if 到达了最后一个格子{
        判断是否只有 n 个皇后，并且每个皇后之间互相不冲突。
        是，则输出答案。
        return ;
    }
    当前格子不放皇后，往下搜索;
    当前格子放皇后，往下搜索;
}

其实可以发现，我们没有必要等到最后再去判断皇后之间是否冲突，在每次选择在当前格子放下皇后时，就可以判断是否有冲突，如果有冲突则直接放弃这个分支，这便是搜索中的剪枝，此案例称为可行性剪枝，即当这次搜索的结果一定不可行时，直接结束这段搜索，流程变为：

void dfs() {
    if 选够了八个皇后{
        输出答案。
        return ;
    }
    if 到达了最后一个格子 {
        return ;
    }
    当前格子不放皇后，往下搜索;
    if 当前格子可以放下皇后并且不冲突 {
        当前格子放皇后，往下搜索;
    }
}

示例代码

int n;
int mp[25][25];  // 用来记录每个皇后是否被选用 
int row[25], col[25], lf[25], rt[25];
// 行是否有皇后，列， 左对角线，右对角线 

void show() {
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if (mp[i][j]) cout << 'Q';
			else cout << '.';
			cout << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}

void dfs(int x, int y, int sum) {
	// x表示现在在第几行，y表示现在在第几列，sum表示选择的皇后的数量 
	if (y == n+1) x++, y=1;  // y到n+1说明这行都试完了 
	if (sum == n) {  
		show();
		return ;
	}
	
	if (x == n+1) return ;  // 到 n+1 说明前面的所有格子都枚举完了。   
	dfs(x, y+1, sum);  // 不选
    // 为什么对角线的下标是 x-y+n 和 x+y，可以
	if (!row[x] and !col[y] and !lf[x-y+n] and !rt[x+y]) {  // 四条线上都没有皇后 
		mp[x][y] = 1;
		row[x] = col[y] = lf[x-y+n] = rt[x+y] = 1;
		dfs(x, y+1, sum+1);
		row[x] = col[y] = lf[x-y+n] = rt[x+y] = 0;
		mp[x][y] = 0;	
	}
}

聪明的你应该能看出，这样每找一个格子，方案数就会翻倍，而棋盘一共有 n×nn \times n 个格子，所以时间复杂度的上界是 2n×n2^{n \times n} 。

第二种思路

再深入思考一层，其实根据题目的限制，每一行、每一列一定都只有一个皇后，那么可以利用这一特点，减少我们要搜索的东西，例如：按一行一行的顺序进行搜索，每次搜索就是尝试在当前行找一个位置放皇后，然后再去搜索下一行，这样做的好处是从搜索一格变成了搜索一行，递归最多 nn 层，搜索树变成了：

image-20240314143039214.png|475

即时间复杂度上界为 O(n!)O(n!)，代码流程：

void dfs() {
    if 所有行都选完了{
        输出答案。
        return ;
    }
	枚举当前行的 n 个位置{
        if 当前位置可以放皇后 {
            放，搜索下一层;
            回溯;
        }
    }
}

示例代码

void dfs(int x) {
	// x表示现在在第几行
	if (x == n+1) {  
		show();  // 与上面代码一致，请自行查看。
		return ;
	}
	for (int i=1; i<=n; i++) {
		if (!col[i] and !lf[x-i+n] and !rt[x+i]) {  // 四条线上都没有皇后
			col[i] = lf[x-i+n] = rt[x+i] = 1;  // 标记有皇后了 
			mp[x][i] = 1;  // 标记这个位置放了皇后 
			dfs(x+1);  // 搜索下一行 
			mp[x][i] = 0;  // 回溯 
			col[i] = lf[x-i+n] = rt[x+i] = 0;
		}
	}
}

为什么这段代码的条件不用判断行是否有冲突呢？因为搜索的顺序正是一行一行来的，所以行是一定不会有冲突的！ 明显能看出，第二种方案的速度是要略快于第一种方案的，在使用DFS去解决问题时，可能会有很多种不一样的思路、想法，最重要的就是想清楚搜索的顺序。

广度优先搜索——BFS

基本概念

广度优先搜索(BFS)可以理解为“雨露均沾”，它就像雷达一样，一层一层的往外进行搜索，它会把当前层的所有节点搜索完后，再去搜索下一层的节点，下图展示了一个可能的广度优先搜索的顺序：

image.png|500

可以发现，在搜索的过程中是没有回溯的过程的，每个节点在用完之后就不会再出现了，也就是先来的节点就先出去了，这是什么的思想呢？没错，正是队列！

如何用队列的思想来具体描述上面的过程呢？如下所示：

节点1入队，此时队列为 [1] 节点1出队，并搜索节点1可以到达的所有节点，找到2和3 节点2和3入队，此时队列为 [2, 3] 节点2出队，并搜索节点2可以到达的所有节点，找到4和5 节点4和5入队，此时队列为 [3, 4, 5] 以此类推。。。

经典例题

例题——走迷宫

题目描述

给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。

数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。

输入格式

第一行包含两个整数 nn 和 mm。 接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

样例输入

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

8

题目分析

如果按照广搜的流程来搜索样例，那么流程如下，数字标号意为在第几层时搜索到这个节点。

image.png|450

代码流程：

初始节点入队;
while (队列不为空) {
	队首元素出队;
	查找所有队首元素可以访问到的节点, 依次入队;
	在查找过程中，可以顺便判断是否到达了终点，是则结束。
}

以上便是BFS代码的简单逻辑，而针对上面这个问题，我们还需要考虑几个点：

[!Question] 思考一下

  1. 对于每个节点，我们需要记录哪些信息？
  2. 如何检测当前元素能访问哪些节点？
  3. 搜索过程中，能否访问之前访问过的节点？如果能，为什么能？如果不能，为什么不能？
  4. 如何判断到达了终点？

对于问题一，我们需要记住当前节点的 位置(几行几列)，以及 到达这个点走了几步。

对于问题二，因为该人只能往上下左右走，所以只需要依次访问当前格子的上下左右四个相邻格，判断能否走即可。

对于问题三，不建议访问，可以试想一下，如果第一步往下走，若可以访问之前的节点，那么第二步必然会有一个往上走的选项，那么搜索过程中就出现了大量多余的分支，降低了代码的效率。 所以，如果要避免这个问题，必然需要标记一下每个节点是否访问过。

对于问题四，如果当前访问的节点位置和终点位置一致，即到达了终点。

根据以上分析，你能尝试把代码写出来么？

示例代码

#include <bits/stdc++.h>
using namespace std;

struct P {
	int x, y, step;  // x,y表示行列，step表示步数 
};
queue<P> q;  // 用来实现广搜的队列 
int n, m;
int mp[105][105], vis[105][105];  // mp存储原始地图
// vis记录对应节点是否被访问过 
int d[5][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
// 方向数组，用来控制上下左右移动。 

void bfs() {
	q.push(P{1, 1, 0});  // 初始节点入队
	vis[1][1] = 1;  // 标记为已访问
	while (!q.empty()) {
		P now = q.front();  // 获取队首元素
		q.pop();  // 队首元素出队
		if (now.x==n and now.y==m) {  // 到达终点 
			cout << now.step << '\n';
			return ;
		} 
		for (int i=0; i<4; i++) {
			int nx = now.x+d[i][0], ny = now.y+d[i][1];  // 计算相邻节点的位置
			if (nx<1 or nx>n or ny<1 or ny>m) continue;  // 越界了不处理 
			if (mp[nx][ny] or vis[nx][ny]) continue;  // 不能走不处理
			q.push(P{nx, ny, now.step+1});  // 节点入队 
			vis[nx][ny] = 1;  // 标记为已访问 
		}
	} 
} 

int main() {
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> mp[i][j];
	bfs();
	return 0;
}

上述代码的时间复杂度为 O(n×m)O(n \times m) ，因为每个点都只会搜索一次，而每个点会产生 44 个子状态。

例题——八数码

题目描述

在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×33×3 的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 3×33×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1−1。

样例输入

2 3 4 1 5 x 7 6 8

样例输出

19

题目分析

因为是只有 x 可以移动，所以可以把 x 的一次交换看作是一次移动，目标是从初始的状态移动到 12345678x 这个状态，问最少交换多少次，实际就是一个求最短路径的问题，只是移动的方式看起来不太一样，如下图所示。

image.png|675

那么要思考的问题其实也很类似：

[!Question] 思考一下

  1. 对于每个节点，我们需要记录哪些信息？
  2. 如何检测当前元素能访问哪些节点？
  3. 搜索过程中，能否访问之前访问过的节点？如果能，为什么能？如果不能，为什么不能？
  4. 如何判断到达了终点？

其一，肯定要记录 当前的棋盘状态、x 的位置、走的步数，关键在于状态如何存储？用二维数组来存当然可以，只是处理起来也稍显麻烦，因为固定是九个字符，所以直接用一个字符串存也是可以的。

其二，无非还是依次尝试把 x 和上下左右四个位置的字符进行交换，注意一下边界问题就好。

其三，肯定是不能访问的，但如何标记这个状态是否出现过呢？可以使用 map 或者 unordered_map 来建立字符串与数字的映射关系，让 map[s] 表示字符串 s 是否出现过，这也是为什么存储的时候要用字符串，也是方便后续使用 map 来标记。

其四，判断当前字符串和结果字符串 12345678x 是否相等即可。

根据以上分析，你能尝试把代码写出来么？

示例代码

#include <bits/stdc++.h>
using namespace std;
struct P {
	string s;  // 当前状态 
	int idx, st;  // idx是x当前的位置，st当前步数 
};
string res="12345678x";
queue<P> q;  // 用于广搜的队列
unordered_map<string, int> mp;  // 用于标记字符串是否出现过
int d[5][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 上下左右

void bfs(string x) {
	q.push(P{x, x.find('x'), 0});
	mp[x] = 1;  // 标记已经走过
	while (q.size()) {
		P now = q.front();
		q.pop();
		if (now.s == res) {  // 判断是否到达终点
			cout << now.st;
			return ;
		}
		for (int i=0; i<4; i++) {
			// 将下标转换为行列形式，这样才好判断边界问题。
			int nx = now.idx/3+d[i][0], ny = now.idx%3+d[i][1], nidx;
			nidx = nx*3 + ny;  // 算出实际的下标
			if (nx<0 or nx>2 or ny<0 or ny>2) continue; 
			string ns = now.s;
			swap(ns[now.idx], ns[nidx]);  // 交换字符
			if (mp[ns]) continue;  // 判断这次的状态是否出现过
			q.push(P{ns, nidx, now.st+1});
			mp[ns] = 1;
		}
	} 
	cout << "-1";
}

int main() {
	char c;
	string x;
	for (int i=1; i<=9; i++) {
		cin >> c;
		x += c;
	}
	bfs(x);
	return 0;
}

总结

BFS实际就像地毯式搜索，一层一层地往外尝试所有可能的路线，这种搜索方式的流程实际就是 先进先出，所以一般BFS都使用队列来存储要搜索的节点；也正是因为这样的搜索方式，BFS在搜索最优解的问题上表现很优秀，例如最短路径、最少操作次数等等。 在使用BFS解决问题时，重点想清楚每个节点的状态应该如何表示，如何搜索到所有可能的新节点并入队，相信把这些设计清楚后，你会非常得心应手。

0 条评论

目前还没有评论...
98
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.0-beta.13 Community