迷宫问题:BFS(队列,最短路径)和DFS(栈

这篇具有很好参考价值的文章主要介绍了迷宫问题:BFS(队列,最短路径)和DFS(栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

搜索的基本算法分为两种:宽度优先搜索(Breadth-First Search,BFS)以及深度优先搜索(Depth-First Search,DFS)。
在学习过程中我们常常会遇到许多需要用搜索解决的问题。比如迷宫。


一、DFS和BFS

BFS:“全面扩散,逐层递进”
DFS:“一路到底,逐步回退”

这次专题主要是对栈和队列的应用进行分析。所以首先我们先简要描述一下DFS和BFS方便大家对下文的例子有更清晰的认识。

  • BFS(Breadth-First Search)宽度优先搜索
    BFS的代码实现可利用队列实现。
    从起点开始,一层一层扩散,先处理完离起点近的,再处理它的下一层。根据这个特点可知它与队列先进先出的特点相吻合。使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
    同时它也非常符合在图上计算最短路径。很多最短路径算法都是由BFS发展而来的。

  • DFS(Depth-First Search)深度优先搜索
    DFS的工作原理则是递归。
    而递归和非递归的转换又可依靠栈进行。所以DFS可以使用栈实现。

二、迷宫问题

1.题目描述

  1. 描述
    一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
    有一个人位于左上角(1,1)处,每次可以向上,下,左,右任意一个方向移动一个单位
    给定一个迷宫,求从左上角走到右下角需要走多少步。
  2. 输入
    第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40)
    接下来是R行,每行C个字符,代表整个迷宫。
    空地格子用’.‘表示,有障碍物的格子用’#‘表示。
    迷宫左上角和右下角都是’.'。即要求从左上角走到右下角
    假设案例为下图5*5的迷宫
    bfs寻找迷宫最短路径,深度优先,算法,图论

2.BFS(队列)解决

  1. 分析
    用BFS的思想来分析这道题。
    当我们每到达一个点的时候都朝四个方向判断其是否能走。这样循环反复,不仅能找到迷宫的出口,同时这个时候所走过的路径也是最短的。
    队列的原理时先进先出(FIFO),而BFS类似于树的层次遍历,从离根结点最近的点开始向下扩散。所以我们需要用队列将最先访问的点先存入,先丢出。
    如下图
    bfs寻找迷宫最短路径,深度优先,算法,图论

  2. 队列实现模板如下
    bfs寻找迷宫最短路径,深度优先,算法,图论

  3. 代码实现如下:

#include<bits/stdc++.h>
using namespace std;
int flag[11][11];//全局变量初始值为0,标记
int x1[4]={0,1,0,-1};//向右,向下,向左,向上
int y2[4]={1,0,-1,0};
int r,c,bex=1,bey=1;//最开始的坐标
char a[44][44];
struct point
{
	int x,y,step;
};
void bfs();
int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
			cin>>a[i][j];
	}
	bfs();
}
void bfs()
{
	queue<point> q;//用来存放可以走的坐标
	struct point begin;
	begin.x=bex;
	begin.y=bey;
	begin.step=1;
	flag[begin.x][begin.y]=1;
	q.push(begin);
	while(!q.empty())
	{
		int x,y,step;
		x=q.front().x;
		y=q.front().y;
		step=q.front().step;
		
		printf("第%d步:(%d,%d)\n",step,x,y);
		if(x==r&&y==c)
		{
			cout<<"总共需要";
			cout<<q.front().step<<"步";
			break;
		}
		for(int i=0;i<4;i++)
		{
			int wx,wy;
			wx=x+x1[i];
			wy=y+y2[i];
			if(a[wx][wy]=='.'&&flag[wx][wy]==0)//可以走且未被走过
			{
				struct point ing;
				flag[wx][wy]=1;
				ing.x=wx;
				ing.y=wy;
				ing.step=q.front().step+1;
				q.push(ing);
			}
		}
		q.pop();
	}
}

运行结果:
bfs寻找迷宫最短路径,深度优先,算法,图论

2.DFS(栈)解决

  1. 分析
    用DFS思想分析。
    当我们开始走迷宫的时候,每次都往同一个方向行走,直到遇到走不通的,就回退一格往另一个方向试探。
    而”回退一格“正是符合栈后进先出的特性。用栈保存所能够到达的每一点坐标。同时可知DFS的实现类似于递归,而栈可以进行非递归的转换.
    遵循右->下->左->上的顺序进行探索。

  2. 栈实现的模板如下
    bfs寻找迷宫最短路径,深度优先,算法,图论

  3. 如图,绿色为正确路线,黄色为回退
    bfs寻找迷宫最短路径,深度优先,算法,图论

代码实现如下):

#include<bits/stdc++.h>
using namespace std;
int flag[11][11];//全局变量初始值为0,标记
int x1[4]={0,1,0,-1};//向右,向下,向左,向上
int y2[4]={1,0,-1,0};
int r,c,bex=1,bey=1;//最开始的坐标
char a[44][44];
struct point
{
	int x,y,direction;
};
stack<point> s;
void dfs();
void print();
int main()
{
	cin>>r>>c;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
			cin>>a[i][j];
	}
	dfs();
	print();
}
void dfs()
{
	int di=0;
	point begin;
	begin={1,1,-1};
	flag[1][1]=1;
	s.push(begin);
	while(!s.empty())//栈不为空时
	{
		int x,y,tx,ty;//tx,ty存储实时坐标;
		x=s.top().x;
		y=s.top().y;
		di=s.top().direction+1; 
		s.pop();
		while(di<4)
		{
	
			tx=x+x1[di];
			ty=y+y2[di];		
			if(flag[tx][ty]==0&&a[tx][ty]=='.')
			{
				flag[tx][ty]=1;
				point now;
				now={x,y,di};
				s.push(now);
				x=tx,y=ty;//更新坐标
				if(x==r&&y==c)
				{
					now={x,y,di};
					s.push(now);
					return;
				}
				else
					di=0;//继续沿着之前的路走
			}
			else di++;//换方向
		}
	}
}
void print()
{
	int i=0;
	point p[1000];
	while(!s.empty())
	{
		p[i++]=s.top();
		s.pop();
	}
	for(int j=i-1;j>=0;j--)
	{
		printf("(%d,%d)\n",p[j].x,p[j].y);//最后在栈中的点
	}
}

运行结果
bfs寻找迷宫最短路径,深度优先,算法,图论


结论

  1. 针对迷宫问题,我们可以根据题目的要求来选择BFS或者DFS来解决。

  2. 两种算法的对比:
    时间复杂度:大多数情况下,两者的是时间复杂度差不多,需要搜索整个空间。
    空间复杂度:DFS使用的空间往往比BFS大 。因为它需要把走过的结点存起来。

  3. 遇到的问题:
    忽略了可以用BFS可以在求最短路径的同时进行所有路径查找。文章来源地址https://www.toymoban.com/news/detail-700962.html

到了这里,关于迷宫问题:BFS(队列,最短路径)和DFS(栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】(BFS/DFS)迷宫路径问题(C语言)

    题目 :现有一迷宫如下图所示,蓝色部分为墙壁,白色部分为通路,入口在左上角(1,1)处,出口在右下角(8,8)处,试找出一条路径以通过该迷宫(路径不能重叠)。 分析 : ① 使用二维数组来存储迷宫,墙用 1 表示,路用 0 表示,如下图所示: 为与题目中的入口坐标

    2024年02月07日
    浏览(83)
  • 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)

    目录 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜) 深度优先搜索(简称“深搜”或DFS) 广度优先搜索 总结 深度优先生成树和广度优先生成树 非连通图的生成森林 深度优先生成森林 广度优先生成森林 图 1 无向图 深度优先搜索的过程类似于树 的先序遍历 ,首先

    2024年01月20日
    浏览(49)
  • 图的遍历(广度优先遍历BFS,深度优先遍历DFS)

    目录 图的遍历概念: 图的广度优先遍历(BFS): 代码实现如下: 测试如下: 注意: 图的深度优先遍历(DFS): 代码实现如下: 测试如下: 总代码: 结语: 给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。\\\"遍

    2024年02月21日
    浏览(56)
  • 【数据结构】图的遍历:广度优先(BFS),深度优先(DFS)

    目录 1、广度优先(BFS) 算法思想  广度优先生成树  知识树  代码实现  2、深度优先(DFS) 算法思想  深度优先生成树 知识树  代码实现           图的广度优先遍历(BFS)是一种遍历图的算法,其思想是从起始顶点开始遍历图,先访问起始顶点的所有直接邻居,然

    2024年02月04日
    浏览(66)
  • 深度优先搜索(DFS)和广度优先搜索(BFS),用代码讲原理

    以图文的形式对深度搜索和广度搜索的理论进行讲解时,可能会对一些概念有些模糊,且不太清楚怎么把该理论用程序的方式进行复现并解决这一搜索问题(这说的就是本人) 。所以后面我看完了一份实现这两种搜索方法的代码,在这做一个笔记,希望对大家有所帮助。 两

    2024年04月12日
    浏览(54)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(51)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 【数据结构】图的创建和深度(DFS)广度(BFS)优先遍历

    图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图, V是图G中 顶点的集合 , E是图G中 边的集合 。 图分为 无向图 和 有向图 无向图: 若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用序偶对(Vi,Vj)表示。 有向图: 若从

    2024年02月05日
    浏览(61)
  • 图的遍历——深度优先搜索(DFS)与广度优先搜索(BFS)(附带C语言源码)

    个人主页:【😊个人主页】 系列专栏:【❤️数据结构与算法】 学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》 第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章 ❤️ 递归 … 在此之前我们学习过了图的一些基本概念,如同在二叉树

    2024年02月06日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包