BFS宽度优先搜索算法,又称广度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
核心思想是:从初始结点开始,应用算符生成第一层结点,检查目标结点是否在这些后继结点中,若没有,再用产生式规则将所有第一层的结点逐一扩展,得到第二层结点,并逐一检查第二层结点中是否包含目标结点。若没有,再用算符逐一扩展第二层所有结点……,如此依次扩展,直到发现目标结点为止 。
宽度优先遍历:
宽度优先遍历的结果:1->2->3->4->5->6->7->8->9->10,用队列存储是12345678910,
宽度优先搜索,其实就是一层一层往下搜索。