3分钟弄懂深度优先搜索[DFS]

深度优先搜索

介绍

假设有这么一张地图：

其中：

• 1 表示墙壁，0 表示可以走的路

🤔 思考：如何找到一条路可以从左上角走到右下角?

左上角的坐标记为(0, 0)，右下角的坐标记为(4, 4)

预处理

准备一个和 map 等大的布尔型二维数组数组 vis，并且全部初始化为false代表没有走过。

其中记录了 map 每个位置是否走过，如果经过一个路就标记为true代表已经走过。

每一次判断四个方向能否走

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

准备四个向量表示四个走的方向:

表示：上下左右

目前的坐标加上向量就可用来表示四个方向。

Coding

#include <vector>
using namespace std;

//map记录地图的墙壁
vector<vector<int>> map = {
		{0, 1, 0, 1, 0},
		{0, 1, 0, 1, 1},
		{0, 0, 0, 0, 1},
		{0, 1, 1, 0, 1},
		{0, 1, 0, 0, 0}
};
//vis记录路径是否走过
vector<vector<bool>> vis(map.size(), vector<bool>(map[0].size(), false));

//方向向量
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

//flag记录是否已经找到一个目标
bool flag = false;

inline void deepSearch(int x, int y) {
	if (flag == true) {
		return;
	}//如果找到一条路径了就不再找了
	if (x == 4 || y == 4) {
		flag = true;
		return;
	}//走到终点就返回

	vis[x][y] = true;//走过的路标记为true

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		//对于接下来的四个方向进行判断
		if (nx < 0 || nx > 4 || ny < 0 || ny > 4) {//判断是否出界
			continue;//判断下一个方向
		}
		if (map[nx][ny] == 0 && vis[nx][ny] == false) {//没有墙壁 并且 没有走过
			deepSearch(nx, ny);
		}
	}
}

int main() {
	//1表示墙壁，0表示可以走的路
	//目标：找到一条(0, 0) -> (4, 4)的路径
	deepSearch(0, 0);
	//这是一个没有做任何事情的深搜
}

🤔 改进

如何打印出路径呢？

几种方法：

1. 将深度优先从递归的系统栈改成手动压栈
2. 记录每个结点的前驱最后倒着找前驱即可
3. 如果当前位置出栈，在vis中设置为false，最后true为走过的路