BFS入门算法笔记

本文主要是介绍BFS入门算法笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

队列

特点:
1、先进先出(FIFO)

2、从队头删除元素

3、在队尾加入元素

队列的创建对象：

queue<元素类型> 队列名；

队列添加元素:队列名. push(元素名）;

去掉队首元素:队列名.pop();

访问队首元素:队列名.front() ;

访问队尾元素:队列名. back();

判断是否为空:队列名.empty();

返回队列大小:队列名.size();

BFS基本思想:
从初始状态S开始，利用规则，生成所有可能的状态，构成树的下一层节点
检查是否出现.目标状态G，若未出现，就对该层所有状态节点，分别依次利用规则,生成再下一层的所有状态节点。
对新一层的所有状态节点继续检查是否出现G，若未出现,继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开，直到出现目标状态为止。

BFS的伪代码：

Node bfs(node source , node target){
memset(visit , 0 ,sizeof(visit));
queue<node> Q;
Q.push(source);
visit[source] = l;
while(!Q.empty()){
Node a = Q.front();
Q.pop();
if(a==target)
{ return a ; }
for(对于a所有的后继节点b)
    if(visit[b])    { continue; }
        Q.push(b) ;
        visit[b] = l;/剪枝，保证节点只进队列一次
    }
    return NULL;
}

这篇关于BFS入门算法笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！