搜索算法3-广度优先搜索(BFS)

广度优先搜索(BFS)

BFS会优先搜索会先搜索到与起始点距离较近的点，而深搜却是沿着一个分支递归到最后。就像是石子掉到水中的水波纹一样扩展开来

举个栗子：

对上图进行深搜按照顶点访问顺序会得到序列:A−B−E−F−C−D−G
对上图进行广搜按照顶点访问顺序会得到序列:A−B−C−D−E−F−G
一般应用：最优解，最小XX
算法思路：
使用队列（queue）来实现：
1. 把起始顶点放到队列中。
2. 每次从队首取出一个顶点，查看这个顶点所有的未访问相邻顶点，把
它们放到队尾。
3. 重复执行第二步操作，直至找到所要找的顶点或者队列为空时结束程
序。
通用模板

void bfs(起始点) {
    将起始点放入队列中;
    while (如果队列不为空) {
        访问队列中队首元素x;
        删除队首元素;
        for (x 所有相邻点) {
            if (该点未被访问过且合法) {
                将该点加入队列末尾;
            }
        }
    }
    队列为空，广搜结束;
}