广度优先搜索(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; }