深搜DFS\广搜BFS 图初步入门
首先,不管是BFS还是DFS,由于时间和空间的局限性,它们只能解决数据量比较小的问题。
深搜,顾名思义,它从某个状态开始,不断的转移状态,直到无法转移,然后退回到上一步的状态,继续转移到其他状态,不断重复,直到找到最终的解。从实现上来说,栈结构是后进先出,可以很好的保存上一步状态并利用。所以根据深搜和栈结构的特点,深度优先搜索利用递归函数(栈)来实现,只不过这个栈是系统帮忙做的,不太明显罢了。
广搜和深搜的搜索顺序不同,它是先搜索离初始状态比较近的状态,搜索顺序是这样的:初始状态---------->一步能到的状态--------->两步能到的状态......从实现上说,它是通过队列实现的,并且是我们自己做队列。一般解决最短路问题,因为第一个搜到的一定是最短路。
下面通过两道简单例题简单的入个门。
深搜例题
poj2386
http://poj.org/problem?id=2386
题目大意:上下左右斜着挨着都算一个池子,看图中有几个池子。
-
W........WW.
-
.WWW.....WWW
-
....WW...WW.
-
.........WW.
-
.........W..
-
..W......W..
-
.W.W.....WW.
-
W.W.W.....W.
-
.W.W......W.
-
..W.......W.例如本图就是有三个池子
采用深度优先搜索,从任意的w开始,不断把邻接的部分用'.'代替,1次DFS后与初始这个w连接的所有w就全都被替换成'.',因此直到图中不再存在W为止。
核心代码:
-
char field[maxn][maxn];//图
-
int n,m;长宽
-
void dfs(int x,int y)
-
{
-
field[x][y]='.';//先做了标记
-
//循环遍历八个方向
-
for(int dx=-1;dx<=1;dx++){
-
for(int dy=-1;dy<=1;dy++){
-
int nx=x+dx,ny=y+dy;
-
//判断(nx,ny)是否在园子里,以及是否有积水
-
if(0<=nx&&nx<n&&0<=ny&&ny<m&&field[nx][ny]=='W'){
-
dfs(nx,ny);
-
}
-
}
-
}
-
}
-
void solve()
-
{
-
int res=0;
-
for(int i=0;i<n;i++){
-
for(int j=0;j<m;j++){
-
if(field[i][j]=='W'){
-
//从有积水的地方开始搜
-
dfs(i,j);
-
res++;//搜几次就有几个池子
-
}
-
}
-
}
-
printf("%d\n",res);
-
}
广搜例题:
迷宫的最短路径
给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四个的通道移动。请求出从起点到终点所需的最小步数。请注意,本题假定从起点一定可以移动到终点。(N,M≤100)('#', '.' , 'S', 'G'分别表示墙壁、通道、起点和终点)
输入:
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
输出:
22
小白书上部分代码:
-
typedef pair<int, int> P;
-
char maze[maxn][maxn];
-
int n, m, sx, sy, gx, gy,d[maxn][maxn];//到各个位置的最短距离的数组
-
int dx[4] = { 1,0,-1,0 }, dy[4]= { 0,1,0,-1 };//4个方向移动的向量
-
int bfs()//求从(sx,sy)到(gx,gy)的最短距离,若无法到达则是INF
-
{
-
queue<P> que;
-
for (int i = 0; i < n; i++)
-
for (int j = 0; j < m; j++)
-
d[i][j] = INF;//所有的位置都初始化为INF
-
que.push(P(sx, sy));//将起点加入队列中
-
d[sx][sy] = 0;//并把起点的距离设置为0
-
while (que.size())//不断循环直到队列的长度为0
-
{
-
P p = que.front();// 从队列的最前段取出元素
-
que.pop();//删除该元素
-
if (p.first == gx&&p.second == gy)//是终点结束
-
break;
-
for (int i = 0; i < 4; i++)//四个方向的循环
-
{
-
int nx = p.first + dx[i],ny = p.second + dy[i];//移动后的位置标记为(nx,ny)
-
if (0 <= nx&&nx < n && 0 <= ny&&ny < m&&maze[nx][ny] != '#'&&d[nx][ny] == INF)//判断是否可以移动以及是否访问过(即d[nx][ny]!=INF)
-
{
-
que.push(P(nx, ny));//可以移动,添加到队列
-
d[nx][ny] = d[p.first][p.second] + 1;//到该位置的距离为到p的距离+1
-
}
-
}
-
}
-
return d[gx][gy];
-
}
经典了两个题结束了,好题链接持续更新。。。。。。
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/81483407
- 点赞
- 收藏
- 关注作者
评论(0)