广度优先搜索BFS&＃xff08;Breadth First Search&＃xff09;也称为宽度优先搜索&＃xff0c;它是一种先生成的结点先扩展的策略。
在广度优先搜索算法中&＃xff0c;解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点&＃xff0c;同时检查目标结点是否在所生成的结点中&＃xff0c;如果不在&＃xff0c;则将所有的第一层结点逐一扩展&＃xff0c;得到第二层结点&＃xff0c;并检查第二层结点是否包含目标结点&＃xff0c;……&＃xff0c;对层次为n&＃43;1的任一结点进行扩展之前&＃xff0c;必须先考虑层次完层次为n的结点的每种可能的状态。因此&＃xff0c;对于同一层结点来说&＃xff0c;求解问题的价值是相同的&＃xff0c;可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。
为了便于进行搜索&＃xff0c;要设置一个表存储所有的结点。由于在广度优先搜索算法中&＃xff0c;要满足先生成的结点先扩展的原则&＃xff0c;所以存储结点的表一般采用队列这种数据结构。
在编写程序时&＃xff0c;可用数组q模拟队列。front和rear分别表示队头指针和队尾指针&＃xff0c;初始时front&＃61;rear&＃61;0。
元素x入队操作为 q[rear&＃43;&＃43;]&＃61;x;
元素x出队操作为 x &＃61;q[front&＃43;&＃43;];
广度优先搜索算法的搜索步骤一般是&＃xff1a;
&＃xff08;1&＃xff09;从队列头取出一个结点&＃xff0c;检查它按照扩展规则是否能够扩展&＃xff0c;如果能则产生一个新结点。
&＃xff08;2&＃xff09;检查新生成的结点&＃xff0c;看它是否已在队列中存在&＃xff0c;如果新结点已经在队列中出现过&＃xff0c;就放弃这个结点&＃xff0c;然后回到第&＃xff08;1&＃xff09;步。否则&＃xff0c;如果新结点未曾在队列中出现过&＃xff0c;则将它加入到队列尾。
&＃xff08;3&＃xff09;检查新结点是否目标结点。如果新结点是目标结点&＃xff0c;则搜索成功&＃xff0c;程序结束&＃xff1b;若新结点不是目标结点&＃xff0c;则回到第&＃xff08;1&＃xff09;步&＃xff0c;再从队列头取出结点进行扩展。
最终可能产生两种结果&＃xff1a;找到目标结点&＃xff0c;或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上&＃xff0c;广度优先搜索算法一定能保证找到一条通向它的最佳路径&＃xff0c;因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径&＃xff0c;则要保存每个结点的来源&＃xff0c;也就是它是从哪一个节点扩展来的。
对于广度优先搜索算法来说&＃xff0c;问题不同则状态结点的结构和结点扩展规则是不同的&＃xff0c;但搜索的策略是相同的。广度优先搜索算法的框架一般如下&＃xff1a;
void BFS&＃xff08;&＃xff09;
{
队列初始化&＃xff1b;
初始结点入队&＃xff1b;
while &＃xff08;队列非空&＃xff09;
{
队头元素出队&＃xff0c;赋给current&＃xff1b;
while &＃xff08;current 还可以扩展&＃xff09;
{
由结点current扩展出新结点new&＃xff1b;
if &＃xff08;new 重复于已有的结点状态&＃xff09; continue;
new结点入队&＃xff1b;
if (new结点是目标状态)
{
置flag&＃61; true; break;
}
}
}
}
对于不同的问题&＃xff0c;用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否为目标结点和是否为重复结点的判断等方面则有所不同。对具体的问题需要进行具体分析&＃xff0c;这些函数要根据具体问题进行编写。
【例1】黑色方块
有一个宽为W、高为H的矩形平面&＃xff0c;用黑色和红色两种颜色的方砖铺满。一个小朋友站在一块黑色方块上开始移动&＃xff0c;规定移动方向有上、下、左、右四种&＃xff0c;且只能在黑色方块上移动&＃xff08;即不能移到红色方块上&＃xff09;。编写一个程序&＃xff0c;计算小朋友从起点出发可到达的所有黑色方砖的块数&＃xff08;包括起点&＃xff09;。
例如&＃xff0c;如图1所示的矩形平面中&＃xff0c;“#”表示红色砖块&＃xff0c;“&＃xff0e;”表示黑色砖块&＃xff0c;“&＃64;”表示小朋友的起点&＃xff0c;则小朋友能走到的黑色方砖有28块。
&＃xff08;1&＃xff09;编程思路
采用广度优先搜索法解决这个问题。
用数组q模拟队列操作&＃xff0c;front为队头指针&＃xff0c;rear为队尾指针&＃xff0c;初始时front&＃61;rear&＃61;0。
入队操作为 q[rear&＃43;&＃43;]&＃61;cur;
出队操作为 cur&＃61;q[front&＃43;&＃43;]。
程序中定义方砖的位置坐标&＃xff08;x,y&＃xff09;为Node类型&＃xff0c;定义数组int
visit[N][N]标记某方砖是否已走过&＃xff0c;visit[i][j]&＃61;0表示坐标&＃xff08;i,j&＃xff09;处的方砖未走过&＃xff0c;visit[i][j]&＃61;1表示坐标&＃xff08;i,j&＃xff09;处的方砖已走过。初始时visit数组的所有元素值均为0。
具体算法步骤为&＃xff1a;
① 将出发点&＃xff08;startx&＃xff0c;starty&＃xff09;入队列q&＃xff0c;且置visit[startx][starty]&＃61;1&＃xff0c;表示该处的方砖已被处理&＃xff0c;以后不再重复搜索。
② 将队列q的队头元素出栈&＃xff0c;得到一个当前方砖cur&＃xff0c;黑色方砖计数&＃xff08;sum&＃43;&＃43;&＃xff09;&＃xff0c;沿其上、下、左、右四个方向上搜索未走过的黑色方砖&＃xff0c;将找到的黑色方砖的坐标入队列q。
③ 重复执行②&＃xff0c;直至队列q为空&＃xff0c;则求出了所有能走过的黑色方砖数。
&＃xff08;2&＃xff09;源程序
#include
using namespace std;
#define N 21
struct Node
{
int x;
int y;
};
int dx[4]&＃61;{-1,1,0,0};
int dy[4]&＃61;{0,0,-1,1};
char map[N][N];
int visit[N][N];
int bfs(int startx, int starty,int w,int h)
{
Node q[N*N],cur,next; // q为队列
int front,rear; // front为队头指针&＃xff0c;rear为队尾指针
int i,x,y,sum;
front&＃61;rear&＃61;0; // 队列q初始化
sum&＃61;0;
cur.x&＃61;startx; cur.y&＃61;starty;
visit[startx][starty]&＃61;1;
q[rear&＃43;&＃43;]&＃61;cur; // 初始结点入队
while(rear!&＃61;front) // 队列不为空
{
cur&＃61;q[front&＃43;&＃43;]; // 队头元素出队
sum&＃43;&＃43;; // 方砖计数
for (i&＃61;0;i<4;i&＃43;&＃43;)
{
x&＃61;cur.x&＃43;dx[i]; y&＃61;cur.y&＃43;dy[i];
if(x >&＃61;0 &&
x&＃61;0 && y&& visit[x][y]&＃61;&＃61;0)
{
visit[x][y] &＃61; 1;
next.x&＃61;x; next.y&＃61;y; // 由cur扩展出新结点next
q[rear&＃43;&＃43;]&＃61;next; // next结点入队
}
}
}
return sum;
}
int main()
{
int i,j,pos_x,pos_y,w,h,sum;
while(1)
{
cin>>w>>h;
if (w&＃61;&＃61;0 && h&＃61;&＃61;0) break;
for(i&＃61;0;i {
for(j&＃61;0;j {
cin>>map[i][j];
if (map[i][j]&＃61;&＃61;&＃39;&＃64;&＃39;)
{
pos_x &＃61; i;
pos_y &＃61; j;
}
visit[i][j] &＃61; 0;
}
}
sum&＃61;bfs(pos_x, pos_y,w,h);
cout< }
return 0;
}
希望对大家有帮助~
学习C/C&＃43;&＃43;编程知识&＃xff0c;想要成为一个更加优秀的程序员&＃xff0c;或者你学习C/C&＃43;&＃43;&＃xff08;数据结构&＃xff09;的时候有难度&＃xff0c;可以关注咨询笔者&＃xff0c;一些学习视频教程以及学习文件都会分享&＃xff0c;而且和别人一起交流成长会比自己琢磨更快哦&＃xff01;
京公网安备 11010802041100号