深度优先搜索 DFS
2024-06-24 11:12:00
发布于：浙江
深度优先搜索 Depth First Search
去年发布的笔记，今年加以改编。
世界上只有两种人，一种是讨厌递归的人，另一种是讨厌递归后又重新爱上递归的人...
搜索算法被广泛的应用在计算机领域中。搜索算法的本质就是通过暴力枚举以及模拟的方式来求得最终的答案。但普通的暴力枚举局限性太大，需要通过学习搜索算法来弥补暴力枚举算法的不足。在学习深度优先搜索算法之前，请务必阅读并掌握递归算法，深度优先搜索的操作是基于递归（函数自己掉用自己）来实现的。深度优先搜索算法常用于解决迷宫问题、图形连通性问题以及在树和图形结构中查找路径等问题。
有一句老话叫做：不撞南墙不回头。这非常形象的刻画出了深度优先搜索的算法策略。以“左手原则”为例，“左手原则”指的是当人们在迷宫中寻找出口时，在每个路口都优先往自己左手边的路口进行探索，如果探索到底都没有找到出口，则回到前一个路口，走自己右手边的路，以此类推，这个动作就被称之为回溯操作。回溯操作即撤销当前动作，继续执行前一个动作。
深度优先搜索算法是通过递归算法来实现的。具体的操作流程从一个节点开始，不断的朝着某一个“路”进行走，直到走到底。如果走到底后没有找的目标解，则回溯到上一个节点换一条“路”继续直走到底。重复上述步骤，直到找到目标解为止。
本文将以下图为例讲述深度优先搜索的一般操作：
**要求：**从节点A开始，通过深度优先搜索的方式找到节点F。
首先，在对上图进行遍历之前，需要确定遍历的顺序：对每一个节点而言，该节点有两个子节点，分别是左子节点和右子节点。因此可以将遍历顺序设定为先访问左节点，如果左节点已经被访问或左节点并不符合条件，则访问右节点。红色节点表示该节点正在被访问，绿色节点表示即将要访问的节点，黑色节点表示该节点已经访问过，不需要再次访问。具体的操作流程如下：
从 A 节点出发，先访问 A 的左节点 B。
从 B 节点出发，先访问 B 的左节点 D。
从 D 节点出发，因为 D 节点自身没有左右节点，因此这条“路”已经走到了尽头，标记点 D 已经被完全访问过并进行回溯操作。先回溯到 D 的父节点 B，因为 B 的左节点已经被访问过，因此再次尝试访问 B 的右节点 E。
从 E 节点出发，因为 E 节点自身没有左右节点，因此这条“路”已经走到了尽头，标记点 E 已经被完全访问过并进行回溯操作。先回溯到 E 的父节点 B。
因为 B 的左右节点都被访问过，则继续回溯到 B 的父节点 A，因为 A 的左节点 B 已经被访问过，因此再次尝试访问 A 的右节点 C。
从 C 节点出发，访问 C 节点的左节点：F 节点。因为 F 节点就是目标查找节点，因此直接返回结果并结束程序即可。
以上就是通过深度优先搜索操作在上图寻找某一个指定节点。对每一个节点而言，都去访问这个节点的左子节点和右子节点，并对该节点的左子节点和右子节点继续进行相同的访问左右节点操作。如果到底都没有找到结果，则进行回溯操作，再次向新的节点出发遍历直到找到最终结果。这符合递归的特性，即一个问题的子问题相似但不相同，因此可以通过递归的方式来解决。
这道题就是一道典型的深度优先图搜索的模板题，题目的大意是从迷宫的左上角出发，判断是否可以走到迷宫的右下角。与前文中的例题不同，这道题是一道地图题，但也可以通过深度优先搜索来实现。先定义地图的任意一个坐标 map[i][j] 为一个节点，那么对于每个节点来说就有四种后继选择，分别是：往上走，往下走，往左走，往右走（在无障碍的情况下）。因此这可以通过递归的方式来模拟每一个节点。
难点一：如何存图？
对于这个地图而言，可以通过构建一个二维数组 arr[50][50] 来保存图中的每一个节点。
int main(){
int n, m;
char arr[50][50];
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> arr[i][j];
}
}
return 0;
}
难点二：如何构造搜索函数？
深度优先搜索的底层原理是通过递归来实现的，因此构造搜索函数需要满足递归的三大要求：
确定递归参数：
在深度优先搜索中，递归的参数往往与节点相同，因此递归可以被等价的看作为每一个节点。在本例中，每一个节点有两个参数，即这个节点的横坐标与纵坐标，因此本递归函数有两个参数，分别也是节点的横坐标与纵坐标。
确定递归返回值：
在本次递归中，并不需要返回一个实际的结果。当程序访问到目标节点，即地图的右下角时，直接输出答案"YES"，并终止程序即可。
确定递归函数体：
递归的函数体就是深度优先搜索中对每一个节点进行的操作。在本题中，每一个节点可以通向自己的上下左右节点（在有路的情况下），因此只需要遍历这个节点所有的可通往节点即可。若一个节点之前已经被访问过，则不需要再次访问该节点，因此需要再开辟一个二维数组 vis[50][50] 来记录某一个节点是否被访问过。当地图中坐标 (i, j) 的节点被访问后，则将这个节点标记为 ，表示已被访问过。
综上所述，本题的递归函数如下：
// 每一层递归都代表一个节点
void dfs(int x, int y){
// 如果这个节点是终点，则终止程序并输出结果。
if (x == n && y == m){
cout << "YES" << endl;
exit(0);
}
// 访问这个节点所通往的所有节点。
// 如果上节点没被访问过且可以被访问，则访问上节点。
if (x - 1 >= 1 && vis[x-1][y] == 0 && arr[x-1][y] == '.'){
// 标记节点已经被访问过。
vis[x-1][y] = 1;
dfs(x-1, y); // 递归上节点。
}
// 如果下节点没被访问过且可以被访问，则访问下节点。
if (x + 1 <= n && vis[x+1][y] == 0 && arr[x+1][y] == '.'){
// 标记节点已经被访问过。
vis[x+1][y] = 1;
dfs(x+1, y); // 递归下节点。
}
// 如果左节点没被访问过且可以被访问，则访问左节点。
if (y - 1 >= 1 && vis[x][y-1] == 0 && arr[x][y-1] == '.'){
// 标记节点已经被访问过。
vis[x][y-1] = 1;
dfs(x, y-1); // 递归左节点。
}
// 如果右节点没被访问过且可以被访问，则访问右节点。
if (y + 1 <= m && vis[x][y+1] == 0 && arr[x][y+1] == '.'){
// 标记节点已经被访问过。
vis[x][y+1] = 1;
dfs(x, y+1); // 递归右节点。
}
return ;
}
本题完整的代码如下，具体讲解见代码注释：
#include <iostream>
#include <algorithm>
using namespace std;
int n, m; // 地图的长和宽。
char arr[50][50]; // 地图。
int vis[50][50]; // 用来记录一个点是否被存放过。
// 每一层递归都代表一个节点
void dfs(int x, int y){
// 如果这个节点是终点，则终止程序并输出结果。
if (x == n && y == m){
cout << "YES" << endl;
exit(0);
}
// 访问这个节点所通往的所有节点。
// 如果上节点没被访问过且可以被访问，则访问上节点。
if (x - 1 >= 1 && vis[x-1][y] == 0 && arr[x-1][y] == '.'){
// 标记节点已经被访问过。
vis[x-1][y] = 1;
dfs(x-1, y); // 递归上节点。
}
// 如果下节点没被访问过且可以被访问，则访问下节点。
if (x + 1 <= n && vis[x+1][y] == 0 && arr[x+1][y] == '.'){
// 标记节点已经被访问过。
vis[x+1][y] = 1;
dfs(x+1, y); // 递归下节点。
}
// 如果左节点没被访问过且可以被访问，则访问左节点。
if (y - 1 >= 1 && vis[x][y-1] == 0 && arr[x][y-1] == '.'){
// 标记节点已经被访问过。
vis[x][y-1] = 1;
dfs(x, y-1); // 递归左节点。
}
// 如果右节点没被访问过且可以被访问，则访问右节点。
if (y + 1 <= m && vis[x][y+1] == 0 && arr[x][y+1] == '.'){
// 标记节点已经被访问过。
vis[x][y+1] = 1;
dfs(x, y+1); // 递归右节点。
}
return ;
}
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> arr[i][j];
}
}
dfs(1, 1); // 递归的调用，从节点(1, 1)开始搜索。
// 如果递归程序结束了，则代表无法到达地图的右下角，固输出NO。
cout << "NO" << endl;
return 0;
}
仔细观察，递归函数的函数体非常的冗余，遍历上下左右四个方向的代码即为相似但不相同，主要的不同点在于需要对四个方向单独进行检测和判断。可以通过用数组记录一个节点横纵坐标的位移来节省代码的空间以及加强代码的可读性。四个方向的横纵坐标偏移量可以大致的写成 dx[] = {-1, 1, 0, 0}; dy[] = {0, 0, -1, 1}。假设上下左右分别被记为 0, 1, 2, 3 。则 dx[i] 和 dy[i]，就分别代表当方向为i时，新节点x坐标和y坐标偏移量。因此，可以通过 for 循环来遍历四个方向并对每一个方向进行统一的判断。修改后的完整代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
char arr[50][50];
int vis[50][50];
int dx[] = {-1, 1, 0, 0}; // 纵坐标偏移量。
int dy[] = {0, 0, -1, 1}; // 横坐标偏移量。
void dfs(int x, int y){
if (x == n && y == m){
cout << "YES" << endl;
exit(0);
}
// 遍历四个方向，对每一个方向进行判断即可。
for (int i=0; i<4; i++){
// 新的节点的横纵坐标。
int cx = dx[i] + x;
int cy = dy[i] + y;
// 判断新节点的横纵坐标是否合法。
if (cx >= 1 && cy >= 1 && cx <= n && cy <= m){
if (vis[cx][cy] == 0 && arr[cx][cy] == '.'){
vis[cx][cy] = 1;
dfs(cx, cy);
}
}
}
return ;
}
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> arr[i][j];
}
}
dfs(1, 1); // 递归的调用，从节点(1, 1)开始搜索。
// 如果递归程序结束了，则代表无法到达地图的右下角，固输出NO。
cout << "NO" << endl;
return 0;
}
本题相较于前一题而言，不仅仅在于判断是否可以从迷宫的起点走到迷宫的终点，而是给定起点坐标和终点坐标，每个方格最多经过一次，记录起点坐标到终点坐标的路径方案的数量。对于本题而言，也可以通过深度优先搜索算法来实现。在本章最开始的例子中（在二叉树中寻找节点F），已经展示了深度优先搜索的具体操作，可以看到，在执行深度优先搜索中，计算机会按照深度优先的方式遍历出所有的路径。因此对于本题而言，只需要记录在深度优先搜索的过程中终点节点被访问过的次数即可。
同时对于本题而言，因为需要统计出从起点到终点的所有路径可能性，则需要进行回溯操作，表示在访问节点之前需要把该节点标记为以访问以防后续的递归继续访问当前节点。同时当该节点被访问完成后，其后继的所有搜索都完成后，需要将节点标记为未访问过以此使得其他的递归程序还可以继续访问该节点。这与 C++ 的递归机制有关，由于递归的底层原理是通过模拟数据结构栈来实现的，因此在弹出当前节点时需要保证后继压入栈的节点不能访问当前被访问过的节点。同时当该递归节点弹出栈后，后续压入栈内的元素则不被该节点所限制。因此完整的代码如下，详情请参照代码注释。
#include <iostream>
#include <algorithm>
using namespace std;
// 分别表示迷宫的长宽、障碍总数以及最终累加结果。
int n, m, k, ans;
// 记录地图，其中arr[i][j]为1表示坐标(i, j)有障碍物。
int arr[50][50];
int vis[50][50]; // 用来记录一个节点是否被访问过。
int dx[] = {-1, 1, 0, 0}; // 纵坐标偏移量。
int dy[] = {0, 0, -1, 1}; // 横坐标偏移量。
int sx, sy, fx, fy; // 起点坐标以及终点坐标。
void dfs(int x, int y){
// 判断是否到达了终点。
if (x == fx && y == fy){
ans += 1; // 对结果进行累加操作。
return ;
}
// 遍历四个方向，对每一个方向进行判断即可。
for (int i=0; i<4; i++){
// 新的节点的横纵坐标。
int cx = dx[i] + x;
int cy = dy[i] + y;
// 判断新节点的横纵坐标是否合法。
if (cx >= 1 && cy >= 1 && cx <= n && cy <= m){
// 判断路是否被走过或是否被有障碍物。
if (vis[cx][cy] == 0 && arr[cx][cy] == 0){
// 标记该节点为访问过。
vis[cx][cy] = 1;
dfs(cx, cy);
// 回溯，取消该节点的访问。
vis[cx][cy] = 0;
}
}
}
return ;
}
int main(){
cin >> n >> m >> k;
cin >> sx >> sy >> fx >> fy;
while(k--){
// 读入障碍物坐标。
int t1, t2;
cin >> t1 >> t2;
arr[t1][t2] = 1; // 表示地图的在坐标(t1, t2)处有障碍物。
}
vis[sx][sy] = 1; // 标记起点被访问过。
dfs(sx, sy); // 递归的调用，从节点(sx, sy)开始搜索。
// 输出最终结果即可。
cout << ans << endl;
return 0;
}
有帮助，赞一个