广度优先搜索(BFS)的原理和应用
二叉树中的层序遍历就属于一种BFS(Board First Search)
层序遍历会得到ABCDEFG的层序优先序列(BFS序列)。在层序遍历过程中，可以注意到先访问的节点的孩子节点必然先被访问(如访问了Ａ后访问Ｂ和Ｃ，那么Ｂ的孩子结点一定在Ｃ的孩子结点前被访问――仅针对下一层的孩子而言)。据这个特性，可以用队列来实现这个遍历。
void Layer(bitree *p)
{
queue<node*> Q; //定义一个队列
node *N;
Q.push(*p); //起始点入队
while(!Q.empty())
{
N=Q.front();
Q.pop();
cout<<N->data<<endl;
if(N->lchild!=NULL) //将扩展子结点(仅一层)全都入队
Q.push(N->lchild);
if(N->rchild!=NULL)
Q.push(N->rchild);
}
}
BFS比它更进一步，可以针对图的结构进行BFS遍历
的BFS(从Ｖ１开始)路径是
广搜的一般结构如下：
定义一个队列;
起始点入队；
while(队列不空){
队头结点出队;
若它是所求的目标状态,跳出循环;
否则，将它扩展出的子结点,全都入队;
}
若循环中找到目标,输出结果;
否则输出无解;
它的主要特点是：
n 每次队头元素出队时，扩展其全部的子结点，并用队列记录下来。
n 搜索过程没有回溯，是一种牺牲空间换取时间的方法。
来看个BFS的经典例子吧Knight Moves zoj(1091)！
题目：国际象棋棋盘上有个马，要跳到指定坐标，求最少的跳的步数！
输入：
a1 h8
输出：
To get from a1 to h8 takes 6 knight moves.
先来看看跳马的规则，马只能往自己在的坐标的2*3或3*2范围内跳动！
例如：要从a1到e4:
第１次所有能跳到的点
第２次所有能跳到的点
第３次所有能跳到的点
当第３次时达到了e4，说明已经达到目的。
以下是我完全可运行的源程序：
#include<iostream>
#include<memory>
#include<queue>
using namespace std;
int dir[8][2]=
{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{-1,-2},{1,-2}
}; //八个可能方向
int flag[8][8]; //标记棋盘中一个点是否已经被踏过
struct node
{
int x,y,step; //棋盘点的坐标和几次可达的信息
};
int main()
{
char a,b,c,d;
node N,P;
queue<node> Q;
memset(flag,0,64);
cin>>a>>b>>c>>d;
int r1=a-'a';
int c1=b-'1';
int r2=c-'a';
int c2=d-'1';
N.x=r1;N.y=c1;N.step=0;
Q.push(N); //初始节点入队
flag[r1][c1]=1;
while(!Q.empty())
{
N=Q.front();Q.pop(); //出队
if(N.x==r2&&N.y==c2) //达到目的，则跳出
break;
for(int i=0;i<8;i++) //八方向搜索
{
int tx=N.x+dir[i][0];
int ty=N.y+dir[i][1];
if(tx>=0&&tx<8&&ty>=0&&ty<8&&flag[tx][ty]==0) //看是否在棋盘内和是否已经被踏过
{
P.x=tx;P.y=ty;P.step=N.step+1;
Q.push(P);
flag[tx][ty]=1; //标记为被踏过
}
}
}
cout<<"To get from "<<a<<b<<" to "<<c<<d<<' ';
cout<<"takes "<<N.step<<" knight moves."<<endl;
}
评论