广度优先搜索(bfs)-创新互联

本文有以下内容:

1. 广度优先搜索的描述

2. 广度优先搜索的优点

3. 广度优先搜索的代码模版

描述:

广度优先搜索算法用于树的遍历。算法的描述概括如下:

1. 取得当前节点

2. 将当前节点入队列

3. 当队列不为空时，获得队头节点head，队头head出队列；

4. 判断队头的状态是否是待求状态

5. 是，则作相应处理；结束算法

6. 不是，将head的所有满足条件的子节点入队列，返回步骤II

广度优先搜索的优点:

  广度优先搜索算法的适用于最短路径之类的问题，由于该算法对状态树的遍历是遵从层序遍历的，所以总是可以保证先找到的是最优的。此外，该算法的在处理某些特殊情况时，需要调整数据结构，调整的方式大致为改队列为优先队列、更改节点的数据结构(如:添加一些变量来对状态进行判断)等；具体的修改方式随需求而变。

广度优先搜索算法的代码模版

void bfs(int x,int y)
{
    node in,out;//此处node为当前节点的数据结构
    queue q;//此处的queue是C++STL中的容器queue
    
    //当前节点入队列
    in.x=x;in.y=y;
    q.push(in);
    //判断当前队列是否为空
    while(!q.empty())
    {
        out=q.front();//取得当前队列的队头
        q.pop();//将队头出队列
        
        if(队头满足条件)
        {
            //作相应处理
            reutrn ;
        }
        else
        {
            while(当前节点out有子节点)
            {
                //获得当前节点out的满足条件的子节点
                //将该子节点入队列
            }
        }
    }
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。