广度优先搜索算法（Breadth-First Search，BFS），

广度优先搜索算法，又称为宽度优先搜索，是一种图形搜索算法。简单的说，BFS 是从根结点开始，沿着树的宽度遍历树的结点。如果所有结点均被访问，则算法中止。该算法常用于树和图的问题中。

让我们先来看第一道经典的题目—— 102. 二叉树的层序遍历

对于树有关的问题，所谓广度优先搜索非常直观，如右下图 ，alt 那么层序遍历就是从树的根节点出发，从上至下，从左至右输出结点。通常在与树有关的问题中，我们可以利用队列来实现BFS。具体实现就是先把根节点放入队列，然后在while循环中访问队头结点，不断将队头结点的左右子节点入队。这样，我们就利用队列先进先出的特性保持了树中每一层结点的相对顺序。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        //队列，广度优先搜索
        if(!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty()){
            vector<int> ans;
            int size = Q.size();//记录该行结点数，方便打印
            for(int i=0; i<size; i++){
                TreeNode *tmp = Q.front();
                Q.pop();
                ans.emplace_back(tmp->val);
                if(tmp->left) Q.push(tmp->left);
                if(tmp->right) Q.push(tmp->right);
            }
            res.emplace_back(ans);
        }
        return res;
    }
};

在这个基础上，再来看第二题——994. 腐烂的橘子

这道题则是图论问题，由于腐烂的橘子只能往上下左右四个方向进行传播，每秒向外传播一层，是一道经典的BFS题目。

解题思路：广度优先搜索（BFS）
1.首先分别将腐烂的橘子和新鲜的橘子保存在两个集合中；
2.模拟广度优先搜索的过程，方法是判断在每个腐烂橘子的四个方向上是否有新鲜橘子，如果有就腐烂它。每腐烂一次时间加 1，并剔除新鲜集合里腐烂的橘子；
3.当橘子全部腐烂时结束循环。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        //BFS,有点像层序遍历
        int m = grid.size(), n = grid[0].size(), min = 0, fresh = 0;
        int dx[4] = {0, 0, -1, 1};
        int dy[4] = {-1, 1, 0, 0};
        queue<pair<int, int>> q;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 1) fresh++;
                else if(grid[i][j] == 2){
                    q.push({i,j});
                }
            }
        }
        while(!q.empty()){
            int size = q.size();
            bool rotten = false;	//判断该轮是否进行了腐烂的传播
            for(int i=0; i<size; i++){
                auto p = q.front();
                q.pop();
                for(int j=0; j<4; j++){
                    int x = p.first + dx[j], y = p.second + dy[j];
                    //找新鲜橘子
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){
                        grid[x][y] = 2;
                        q.push({x, y});
                        rotten = true;
                        fresh--;
                    }
                }
            }
            if(rotten) min++;
        }
        return fresh == 0 ? min : -1;
    }
};

总结

所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。该类问题通常可以通过队列进行层次的遍历。