目录：

一、摘要

二、关键词

三、广度优先搜索算法概述

四、广度优先搜索算法的应用领域

五、广度优先搜索算法的具体实现过程

六、教学中广搜算法的难点

七、图解广度优先搜索算法的优点及其例子

八、参考文献

一、摘要：

广度优先搜索算法（BFS，Breadth First Search），是算法竞赛中的常用必修的一种搜索算法，该算法思路清晰，应用范围广范，是一种实用的寻路搜索算法。在高中算法学习中，初学者对该算法搜索过程的理解有一定的难度，图解广度优先搜索算法，能够很好的解决这一问题。

二、关键词

广度优先搜索算法、宽度优先搜索算法、BFS、搜索、算法教学

三、广度优先搜索算法概述

广度优先搜索算法（BFS，Breadth First Search）又称宽度优先搜索算法，它是一种按照广度或宽度进行搜索的一种算法，广度优先搜索算法的算法思路清晰，是一种简便的图的搜索算法，该算法的的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。^[1]

四、广度优先搜索算法的应用领域

广度搜索算法是一种具有广泛适用性的搜索算法，它适合解决树或图上搜索目标的情况，很多熟悉的问题都可用广度优先搜索算法来解决，比如八数码问题、求最短路径问题、走迷宫问题等等。

五、广度优先搜索算法的具体实现过程

广度优先搜索算法从起始节点开始，按照层次进行搜索。使用队列方式进行实现，将当前队首节点未访问过的子节点加入到队列中，判断新加入的节点是否是目标节点，如果是，则成功搜索到，如果不是，则继续进行同样的入队出队操作。其具体实现过程如下伪代码：

int bfs()

{

初始化，初始状态存入队列；

队列首指针head=0; 尾指针tail=1；

do

 {

    指针head后移一位，指向待扩展结点；

    for (int i=1;i<=max;++i)                  //max为产生子结点的规则数

     {

      if (子结点符合条件)

         {

           tail指针增1，把新结点存入列尾；

           if (新结点与原已产生结点重复) 删去该结点（取消入队，tail减1）;

   else

       if (新结点是目标结点) 输出并退出；

              }

         }

}while(head队列为空

}

六、教学中广度优先搜索算法的难点

在初学算法的过程中，广度优先搜索算法思路清晰，易于理解，但初学者对广度优先搜索具体搜索过程往往比较笼统，这不利于其真正理解该算法，采用图解的方法，把广度优先搜索的过程直观的呈现出来，可以帮助初学者更加容易的理解该算法。

七、图解广度优先搜索算法的优点及其例子

下面我们通过图解八数码问题的实例来理解广度优先算法。

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

现假定初始状态为：

2	8	3
1	6	4
7		5

目标状态为：

1	2	3
8		4
7	6	5

按照广度优先搜索算法的思路，根据左、上、右、下的规则八数码的图解过程如下：

 

八数码问题的宽度优先搜索步骤如下：

1、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步；

2、由初始节点向第1层扩展，得到3个节点：2、3、4；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若2、3、4节点均不是目标节点则转到第3步；

3、从第1层的第1个节点向第2层扩展，得到节点5；从第1层的第2个节点向第2层扩展，得到3个节点：6、7、8；从第1层的第3个节点向第2层扩展得到节点9；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若6、7、8、9节点均不是目标节点则转到第4步；

4、按照上述方法对下一层的节点进行扩展，搜索目标节点；直至搜索到目标节点为止。^[2]

用C++代码实现时使用0代替空格输入，输出时亦然，具体代码如下：

#include

#include

#include

using namespace std;

struct node{ int map[5][5],wi,wj,t; } f[1000001];

int dx[4]={0,-1,0,1};

int dy[4]={-1,0,1,0};

int xd[5][5]={0,0,0,0,0,

          0,1,2,3,0,

           0,8,0,4,0,

           0,7,6,5,0,

           0,0,0,0,0};

int nz[5][5];

int cnt;

int zp(int tou)

{

    for(int i=1;i<=3;i++)

    {

        for(int j=1;j<=3;j++)

        {

            if(f[tou].map[i][j]!=xd[i][j])

            {

                return false;

            }

        }

    }

    return true;

}

bool pdc(int wei)

{

    for(int i=1;i<=wei;i++)

    {

        bool flag=true;

        for(int j=1;j<=3;j++)

        {

            for(int k=1;k<=3;k++)

            {

                if(f[i].map[j][k]!=nz[j][k])

                {

                    flag=false;

                    break;

                }

            }

            if(flag==false)

            {

                break;

            }

        }

        if(flag==true)

        {

            return false;

        }

    }

    return true;

}

void bfs()

{

    int tou=1,wei=2;

    while(tou

    {

        if(zp(tou)==true)

        {

         cnt=tou;

            return ;

        }

        for(int i=0;i<=3;i++)

        {

            int nx=f[tou].wi+dx[i];

            int ny=f[tou].wj+dy[i];

            if(nx>=1 && nx<=3 && ny>=1 && ny<=3)

            {

                memset(nz,0,sizeof(nz));

                for(int j=1;j<=3;j++)

                {

                    for(int k=1;k<=3;k++)

                    {

                        nz[j][k]=f[tou].map[j][k];

                    }

                }

                nz[f[tou].wi][f[tou].wj]=f[tou].map[nx][ny];

                nz[nx][ny]=0;

                if(pdc(wei)==true)

                {

                    for(int j=1;j<=3;j++)

                    {

                        for(int k=1;k<=3;k++)

                        {

                            f[wei].map[j][k]=nz[j][k];

                        }

                    }

                    f[wei].t=f[tou].t+1;

                    f[wei].wi=nx;

                    f[wei].wj=ny;

                    wei++;

                }

            }

        }

        tou++;

    }

}

int main()

{

    for(int i=1;i<=3;i++)

    {

        for(int j=1;j<=3;j++)

        {

            scanf("%d",&f[1].map[i][j]);

            if(f[1].map[i][j]==0)

            {

                f[1].t=0;

                f[1].wi=i;

                f[1].wj=j;

            }

        }

    }

    bfs();

    for(int i=1;i<=cnt;i++){

     cout<<"第"<<i<<"次广度优先搜索："<<endl;

     for(int j=1;j<=3;j++)

                {

                    for(int k=1;k<=3;k++)

                    {

                        cout<<f[i].map[j][k]<<" ";

                    }

                    cout<<endl;

                }

}

    return 0;

}^[3]

八、参考文献

[1]董永建.信息学奥赛一本通[M].科学技术文献出版社:北京市海淀区复兴路,2016-07-01:296.

[2]宁静以致远.八数码难题（8 puzzle）深度优先和深度优先算法[EB/OL].https://www.cnblogs.com/luoht/archive/2011/02/26/1965724.html,2011-02-26.

[3]zhongzijun.题解 P1379 【八数码难题】[EB/OL].https://www.luogu.com.cn/blog/zzj/ti-xie-p1379-ba-shu-ma-nan-ti-post,2017-12-31.