广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历策略。它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。

BFS算法是利用队列实现的一种搜索算法，逐层向下遍历，从一个点像四周扩散（将可选节点存放于队列中，删除已被使用的节点），使用队列完成操作，通常用于最短路径的寻找。。

一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。

BFS 的应用一：层序遍历

层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

BFS 的应用二：最短路径

在二叉树中，BFS 可以实现一层一层的遍历。在图中同样如此。从源点出发，BFS 首先遍历到第一层结点，到源点的距离为 1，然后遍历到第二层结点，到源点的距离为 2…… 可以看到，用 BFS 的话，距离源点更近的点会先被遍历到，这样就能找到到某个点的最短路径了。

BFS适合此类题目：给定初始状态跟目标状态，要求从初始状态到目标状态的最短路径。

Dijkstra 算法解决的是带权最短路径问题，而我们这里关注的是无权最短路径问题。也可以看成每条边的权重都是 1。这样的最短路径问题，用 BFS 求解就行了。

BFS 的常用模板

1.如果不需要确定当前遍历到了哪一层，模板如下：

下述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

void bfs() {
 vis[] = {0}; // or set
 queue<int> pq(start_val);

 while (!pq.empty()) {
     int cur = pq.front(); 
     pq.pop();
     for (遍历cur所有的相邻节点nex) {
         if (nex节点有效 && vis[nex]==0){
             vis[nex] = 1;
             pq.push(nex)
         }
     } // end for
 } // end while
}

2.如果需要确定遍历到哪一层，模板如下：

void bfs() {
 int level = 0;
 vis[] = {0}; // or set
 queue<int> pq(original_val);
 while (!pq.empty()) {
     int sz = pq.size();

     while (sz--) {
         int cur = pq.front(); 
         pq.pop();
         for (遍历cur所有的相邻节点nex) {
             if (nex节点有效 && vis[nex] == 0) {
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end inner while
     level++;

 } // end outer while
}