BFS理解入门

宽度优先搜索(Breath frist search )
用队列实现：

给一个图：
开始位置 （1,1),0代表可以走，1代表不可以走，最终到（4,6)位置
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
操作：
最初一步：从位置(1,1)压入队列
之后进入while(!q.empty())循环操作，先得到队列头元素即(1,1)然后将队列
头元素删掉，然后判断得到的头元素是不是我们所要的目的坐标即(4,6),是的话
输出结束操作，反则，向四周扩散，en.step=st.step+1
进入for循环操作，for循环可以实现向四周扩散一步的操作，但因为限制条件的
缘故最多扩散四步，将每次扩散的压入队列里即可，直到找到目的坐标
图2：
1 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
图3：
1 1 1 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
图4：
1 1 1 1 0 0
1 1 1 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
最终能扩散到目标位置得到最终步数，而一个坐标周围的步数是一样的.
所以BFS的原理：通过向四周进行扩散，将每个点到初始位置的距离记录下来，
然后将所有点压入队列，然后从队列中取出，查找目标点，然后将目标点到初始
位置的点的距离输出即可

列题
最短步数：http://nyoj.top/problem/58
AC代码：

#include<bits/stdc++.h>
using namespace std;
int Map[10][9]=
{
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1
};//存图
int book[20][20];
int dir[4][2]= {0,1,1,0,0,-1,-1,0}; //移动方向
int n,m,ex,ey,sx,sy;
struct node
{
int x,y,step;//坐标
} st,en;
queue <node>q;
void bfs(int i,int j)//初始坐标
{
st.x=i;//初始位置
st.y=j;
st.step=0;
q.push(st);//将起点坐标压入
while(!q.empty())
{
st=q.front();//将头元素置头,得到头元素
q.pop();//将头元素删掉
if(st.x==ex&&st.y==ey)//判断当前位置是不是我们的目标位置
{
printf("%dn",st.step);
return ;
}
//如果不是
en.step=st.step+1;//步数加一,这里的en.step其实就是st.step,之前的操作
for(int i=0; i<4; i++)
{
en.x=st.x+dir[i][0];
en.y=st.y+dir[i][1];
if(en.x<0||en.y<0||en.y>8||en.x>8||book[en.x][en.y]||Map[en.x][en.y])//限制条件
continue;
book[en.x][en.y]=1;//标记走过的下次不在压入
q.push(en);//压入坐标,每回最多压入四个坐标，即图的四周的坐标
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
while(!q.empty())
q.pop();
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
book[sx][sy]=1;
bfs(sx,sy);
memset(book,0,sizeof(book));
}
}

最后

以上就是懦弱刺猬为你收集整理的BFS理解入门的全部内容，希望文章能够帮你解决BFS理解入门所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。