首页 > 代码库 > 宽度优先搜索
宽度优先搜索
Breadth First Search
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
与树的层序遍历一样 遍历结果为 1 2 3 4 5 6 。。。。。21 22
操作:
根节点入队;
while(队非空)
{
拿出队首元素进行操作;
队首可到达的结点入队;
删除队首;
}
以上图为例:
1入队;
2 3 4 5 入队;1出队;
6入队;2出队;
7 8 9入队;3出队;
4出队;
10 11 入队;5出队;
。。。。。。
以此类推直到满足条件结束搜索。
宽度优先搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。