- 介绍
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和 Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
- 遍历二叉树
//伪代码
bfs(){
queue<int> q;
//从根节点开始搜索
q.push(Start);
while(!q.Empty()){
//从队列头部弹出一个元素
ele = q.front();
q.top();
//输出元素
//print ele
//有左节点,就加入到队列中,右节点同理
if(q.left != NULL){
q.push(q.left);
}
if(q.right != NULL){
q.push(q.right);
}
}
}
- 遍历图
//TODO
- 更一般的搜索
这一点我们和遍历二叉树的时候进行对比可以发现,二叉树每遍历一个节点最多可以在遍历下一层的时候产生两个子节点, 而对于普适情况是,我们每遍历一个节点,可以产生任意个子节点个数,这也是我们需要一个队列的原因。
更进一步,如果我们维护一个优先队列,可能更有效的寻找到答案。
//伪代码描述
创建一个队列q
根节点入队
while q不为空 {
取出一个元素elem
对元素elem进行处理
while elem有子节点p {
if 需要剪子p {
continue
}
将p加入到队列q中
}
}
- 去重(修枝)
状态转移的时候可能转移到之前的状态,这样就形成了一个环,我们需要一个容器来保存已经搜索过的状态,这样我们可以把这一个节点的枝叶全部去掉。