深度优先搜索与广度优先搜索大佬们教教我呗
2024-06-01 21:37:43
发布于:广东
深度优先搜索,简称DFS
初始节点出发,按预定的顺序扩展到下一个节点,然后从下一节点出发继续扩展新的节点,不断递归执行这个过程,直到某个节点不能再扩展下一个节点为止。此时,则返回上一个节点重新寻找一个新的扩展节点。如此搜索下去,直到找到目标节点,或者搜索完所有节点为止。
原文链接-传送门
广度优先搜索,简称BFS
它是一种图搜索算法,它通过逐层遍历图的节点来查找目标
或许有些人会认为它跟深搜差别不大,但我想说你错了,深搜和广搜有着一些共同点但更多的是不同点,下面我就分开讲讲:
深度优先搜索(DFS):
简单来说就是走迷宫,给定一个入口和一个出口,问你能不能走出去,如果能输出"YES",不能输出"NO"
你可以选择往前走,直到遇到死胡同,然后再回头,选择另外一个方向继续前进,直到找到出口。这个过程,就是深度优先搜索的一个形象展现。
但广搜就会简单很多:
广度优先搜索(BFS):
它的特点是一层一层地进行搜索,每一层的节点都会被访问到,然后再进入下一层。这种方式就好比我们在寻找某个城市的地铁站,先从起点站开始,然后逐站寻找,直到找到目标站为止。
你可以理解为我要找我的朋友,我就可以先从XX区找起,在找到了之后再在XX区内找小区,接着再往下执行该操作,最终找到朋友,这就是广搜的一种体现
深度优先搜索,如同其名,它的特点是尽可能深地搜索树的分支。这种策略在搜索大树时非常有效,因为它可以快速找到解决方案,或者在没有解决方案的情况下,快速排除某些路径。然而,这种策略也有其局限性,例如,它可能会在搜索过程中陷入无限循环。为了避免这种情况,我们通常需要在实现深度优先搜索时,加入一些特殊的检查机制。
广度优先搜索则是一种层次遍历的策略,它会先搜索离根节点最近的节点,然后再搜索下一层的节点。这种策略在搜索最短路径问题时非常有效,因为它总是先搜索离根节点最近的路径,所以一旦找到解决方案,那么这个解决方案就是最短的。然而,广度优先搜索需要存储所有的节点,因此在空间复杂度上,通常会比深度优先搜索要大。
让我们通过一个实际的例子来理解这两种搜索策略。假设我们想要找到从A地点到B地点的路线。如果我们使用深度优先搜索,那么我们可能会先找到一条从A到B的路线,但这条路线可能不是最短的。如果我们使用广度优先搜索,我们会先找到所有从A出发可以到达的地点,然后再从这些地点出发,找到可以到达B的地点。这样,我们找到的第一条路线,就是最短的路线。
在实际的应用中,我们应该根据问题的特性,选择最适合的搜索策略。例如,如果我们需要找到所有可能的解决方案,那么深度优先搜索可能会更有效。而如果我们需要找到最短的解决方案,那么广度优先搜索可能会更合适。
原文链接-传送门
接下来聊聊代码:
深度优先搜索:
题目描述
一个迷宫由 n 行 m 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从点 A (sx,sy) 走到点 B (fx,fy) 是否能走通,A 和 B 点都是空地。
提示
1≤n,m≤40,1≤sx、fx≤n,1≤sy、fy≤m
输入格式
第一行是两个整数,n 和 m,代表迷宫的长和宽。
第二行是四个整数,分别表示 sx,sy,fx,fy。
接下来是 n 行,每行 m 个字符,代表整个迷宫。
空地格子用 . 表示,有障碍物的格子用 # 表示。
样例组输入#1
5 5
1 1 5 5
..###
#....
#.#.#
#.#.#
#.#..
样例组输出#1
YES
---以下内容来自:小码王学习软件https://online.xiaomawang.com/:深度优先搜索(二)作业第一题
代码:
#include<bits/stdc++.h>
using namespace std;
char a[15][15];
bool vis[15][15];
int n,m,sx,sy,ex,ey;
int f;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
//显示各个方位,在dx=0 dy=1的情况下也就是说左右不变往上走一格
void dfs(int x,int y){
vis[x][y]=1;
if(x==ex&&y==ey){
f=1;
return ;
}
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!='#'&&vis[xx][yy]==0){
dfs(xx,yy);
}//判断是否能走,如果可以就标记
}
}
int main(){
cin>>n>>m;
cin>>sx>>sy>>ex>>ey;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dfs(sx,sy);
if(f==1){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
紧接着是 广度优先搜索
题目描述
一个迷宫由 R 行 C 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
提示
数据范围:
(1≤R,C≤40)
样例说明:
移动路径为 [1,1]−>[1,2]−>[2,2]−>[2,3]−>[2,4]−>[3,4]−>[4,4]−>[5,4]−>[5,5],一共花费8步
输入格式
第一行是两个整数,R 和 C(1≤R,C≤40),代表迷宫的长和宽。
接下来是 R 行,每行 C 个字符,代表整个迷宫。
空地格子用‘.’表示,有障碍物的格子用 ‘#’ 表示。
迷宫左上角和右下角都是‘.’。
输出格式
输出从左上角走到右下角最小移动的步数。计算步数不包含起点。
样例组输入#1
5 5
..###
#....
#.#.#
#.#.#
#.#..
样例组输出#1
8
---以下内容来自:小码王学习软件https://online.xiaomawang.com/:广度优先搜索(一)第二模块广度优先搜索第二题
代码:
#include<bits/stdc++.h>
using namespace std;
char MAP[49][49];
bool vis[49][49];
struct node{
int x,y,step;
}l,r;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>MAP[i][j];
}
}
queue<node> q;
q.push({1,1,0});
vis[1][1]=1;
while(q.size()){
r=q.front();
q.pop();
if(r.x==n&&r.y==m){
cout<<r.step;
break;
}
for(int i=0;i<4;i++){
l.x=r.x+dir[i][0];
l.y=r.y+dir[i][1];
l.step=r.step+1;
if(l.x>=1&&l.x<=n&&l.y>=1&&l.y<=m&&!vis[l.x][l.y]&&MAP[l.x][l.y]=='.'){
vis[l.x][l.y]=1;
q.push(l);
}
}
}
return 0;
}
最后说说心得,八个字:
再也不想见到它了
注:抄的我都标记了,不信自己查
这里空空如也
有帮助,赞一个