【数据结构与算法】—— * 深度优先搜索入门 (二) *

xavier 发布于2021-11-18 10:02 / 1029人阅读

摘要：小澈知道后便去解救无助的小玄。小澈是有备而来，已经弄清楚了迷宫的地图，现在小澈要以最快的速度去解救小玄。而小澈在某个点的时候需要处理的是先检查小澈是否到达了小玄的位置，如果没有到达则找出下一步可以走的地方。

问题引入

有一天，小玄一个人去玩迷宫，但是方向感很不好的他迷路了。小澈知道后便去解救无助的小玄。小澈是有备而来，已经弄清楚了迷宫的地图，现在小澈要以最快的速度去解救小玄。问题开始了......

迷宫由n行m列的单元格组成（n,m < 50），每个单元格要么是空地，要么是障碍物。

你的任务是帮小澈找到一条从迷宫的起点到小玄所在位置的最短路径。

注意障碍物是不能走的，也不能走到迷宫外哦。

问题解析

首先我们可以用一个二维数组来储存这个迷宫。刚开始时小澈位于迷宫的入口处（1,1），小玄在（p,q）,最开始只能向右或者是向下走。

现在只有一个小澈，我们只能一个一个去尝试。我们可以先让小澈往右走，直到走不通时再回到这里。这里我们规定一个顺序，按照顺时针的方向来尝试（即按照右，下，左，上的顺序去尝试）。

第一次尝试后的结果如下：

我们这样只是尝试了一条路，并不一定是最短的。在刚才的很多地方我们有很多选择方向都是可以有多重选择的，所以我们需要把所以的选择都尝试一遍，最后输出最短的一条路径。

代码实现

现在我们尝试用深度优先搜索的方式来解决这个问题。来看看dfs这个函数怎么写。

dfs函数

dfs函数的功能是用来解决当前应该怎么办。而小澈在某个点的时候需要处理的是：先检查小澈是否到达了小玄的位置，如果没有到达则找出下一步可以走的地方。

为了解决这个问题，dfs函数需要维护三个参数，分别是

当前这个点的x坐标
当前这个点的y坐标
当前已经走过的步数step
void dfs(int x, int y, int step){	return;}
判断是否已经到达小玄的位置这一点很好实现，只需要判断当前的坐标是否和小玄的位置相等即可
void dfs(int x, int y, int step){	//判断是否到达小玄的位置	if (x == p && y == q)	{		//更新最小值		if (step < min)			min = step;		return;   //请注意这里的返回很重要	}	return;}
如果我们没有到达小玄的位置，则找出下一步可以走的地方。因为有四个方向可以走，根据我们之前的约定，按照顺时针的方向来尝试（即按照右，下，左，上的顺序去尝试）。为了编程方便，我们定义了一个方向数组next,如下：
int next[4][2] = {{0,1},	//向右走				{1,0},		//向下走				{0,-1 },	//向左走			    {-1,0}		//向上走};
通过这个方向数组，使用循环我们就能很容易的获得下一步的坐标。这里将下一步的横坐标用tx存储，纵坐标用ty来存储。
for (k = 0; k <= 3; k++){	//计算下一个点的坐标	tx = x + next[k][0];	ty = y + next[k][1];}
接下来我们要对下一个点的（tx,ty）进行一些判断。包括是否越界，是否为障碍物，以及这个点是否在路径中（避免重复访问一个点）。需要用一个book[tx][ty]来记录格子（tx,ty）是否已经在路径中。

如果这个点符合要求，就对这个点进行下一步的扩展，即dfs(tx,ty,step+1)，注意这里是step+1，因为你一旦从这个点开始往下继续尝试，就意味着你的步数已经增加了1.

代码实现如下：
for (k = 0; k <= 3; k++){	//计算下一个点的坐标	tx = x + next[k][0];	ty = y + next[k][1];	//判断是否越界	if (tx < 1 || tx > n || ty < 1 || ty > m)		continue;	//判断该点是否为障碍物或者已经在路径中	if (a[tx][ty] == 0 && book[tx][ty] == 0)	{		book[tx][ty] = 1;		//标记这个点已经走过		dfs(tx, ty, step + 1);	//开始尝试下一个点		book[tx][ty] = 0;		//尝试结束，取消这个点的标记	}}

完整代码

#include int n, m, p, q, min = 99999999;int a[51][51], book[51][51];void dfs(int x, int y, int step){	int next[4][2] = { {0,1},	//向右走				{1,0},		//向下走				{0,-1 },	//向左走				{-1,0}		//向上走	};		int tx, ty, k;	//判断是否到达小玄的位置	if (x == p && y == q)	{		//更新最小值		if (step < min)			min = step;		return;   //请注意这里的返回很重要	}	//枚举四种走法	for (k = 0; k <= 3; k++)	{		//计算下一个点的坐标		tx = x + next[k][0];		ty = y + next[k][1];		//判断是否越界		if (tx < 1 || tx > n || ty < 1 || ty > m)			continue;		//判断该点是否为障碍物或者已经在路径中		if (a[tx][ty] == 0 && book[tx][ty] == 0)		{			book[tx][ty] = 1;		//标记这个点已经走过			dfs(tx, ty, step + 1);	//开始尝试下一个点			book[tx][ty] = 0;		//尝试结束，取消这个点的标记		}	}	return;}int main(){	int i, j, startx, starty;	//读入n和m，n为行，m为列	scanf("%d %d", &n, &m);	//读入迷宫	for (i = 1; i <= n; i++)	{		for (j = 1; j <= m; j++)			scanf("%d", &a[i][j]);	}	//读入起点和终点的坐标	scanf("%d %d %d %d", &startx, &starty, &p, &q);	//从起点开始搜索	book[startx][starty] = 1;  //标记起点已经在路径中，防止后面重复走	//第一个参数是起点的x坐标，第二个参数是起点的y坐标，第三个参数是初始步数为0	dfs(startx, starty, 0);	//输出最短步数	printf("%d", min);	getchar(); getchar();	return 0;}

总结

发明深度优先算法的John E.Hopcroft 和 Robert E .Tarjan.1971~1972年，他们在斯坦福大学研究图的连通性（任意两点是否可以互相到达）和平面性（图中所有的边不交叉。在电路板上设计布线的时候，要求线和线不能交叉。这就是平面性的一种应用）

今天的内容就分享到这啦！！

如果觉得有帮助，请：

服务器托管超融合服务器深度优先搜索最佳优先搜索算法广度优先搜索算法代码广度优先搜索

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123702.html

《算法和数据结构》总纲，五个阶段，一个目标，坚持就是胜利，冲！ (建议自学)

摘要：点击我跳转末尾获取粉丝专属算法和数据结构源码。来看第一个语言程序我的第一个程序这段代码只做了一件事情，就是向屏幕上输出一行字。是一个头文件标准输入输出头文件是一个预处理命令，用来引入头文件。作为函数的返回值。 ...

YJNldm 2021-09-30 09:47 评论0 收藏0
【数据结构与算法】—— * 深度优先搜索入门 *

摘要：问题引入输入一个数，输出的全排列问题解析假设有编号为的张扑克牌和编号为的个盒子。至于下一步该如何做，则与当下该如何做是一样的。基本模型判断边界尝试每一种可能继续下一步的尝试返回每一种尝试就是一种扩展。问题引入输入一个数n，输出1~n的全排列问题解析假设有编号为1,2,...

hikui 2021-11-16 11:44 评论0 收藏0
面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
学习JavaScript数据结构与算法 — 深度优先搜索算法

摘要：深度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。用深度优先搜索算法对图中的任务图进行拓扑排序最终各顶点的发现和探索完成时间会保存在中。深度优先搜索（DFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中深度优先搜索算法会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点，接着原路回退并探索下一条路径。换句话说，它是先深度后广...

李增田 2019-08-22 11:09 评论0 收藏0
SegmentFault 技术周刊 Vol.31 - 码农也要学算法

摘要：记作称为算法的渐进时间复杂度，简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构，可以存储有序的元素集合。首先在大的分类上，它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候，意味着我们正步入一个算法的时代。计算...

cgspine 2019-06-26 15:45 评论0 收藏0