广度优先搜索类似二叉树的层次遍历，它的基本思想是：首先访问顶点v，接着由v出发，依次访问v的邻接节点w1,w2,.然后再依次访问w1,w2..的邻接节点。BFS不像DFS那样存在后退的情况，它不是递归的。为了实现逐层访问，算法还需要一个辅助队列来存储其已经访问过的节点，进而才能访问它的下一层节点。
如图：

graph

对于上图：BFS将产生如下的遍历：
abddefgh
其伪代码流程是：

bool visted[NODES_NUMS];
void BFS_T(Graph G){
set visted as False
init Queue Q
for(int v=0;i<G.nodes_nums;v++)
if(!visted[v])  
      BFS(G, i);
  }
}

void BFS(Graph G, int v){
  visted[v] = True //初始化访问顶点
  enqueue(Q,v)
  while(!Q.empty()){
      dequeue(Q,v)
      for(w in v's edge nodes){//依次访问v的邻接节点
             if(!visted(w)){
                visted[w] = True
                enqueue(Q,w)
              }
        }
  }  
}

在最坏的情况下，BFS的遍历时间复杂度为

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

• Example 1:Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
• Example 2:Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

---

题意：给定一个正整数，找到最少的完美平方数之和，使其等于这个正整数.

• 思路1：BFS
  找到平方小于n的所以数字，之后每个数字相应的向后拓展，找到最终和等于n的层数

  
  树形思路

class Solution {
public:
    int numSquares(int n) {
        int tmp = int(sqrt(n));
        vector<int> square_element;
        queue<int> square_queue;
        int level = 1;
        
        if(n<1)
            return 0;

        for(int i=1;i<=tmp;i++)
            square_element.push_back(i*i);
        for(auto item:square_element)
            square_queue.push(item);
        square_queue.push(-1);

        while(!square_queue.empty()){
            while(square_queue.front()!=-1){
                tmp = square_queue.front();
                if(tmp==n)
                    return level;
                for(auto item:square_element)
                    square_queue.push(item+tmp);
                square_queue.pop();
            }
            square_queue.pop();
            square_queue.push(-1);
            level++;
        }while(0)Hotwords.str*p

        return -1;
    }
};

• 思路2:动态规划
  已知任何一个整数都可以被四个以内的平方数之和组成
  
  
  
  
  
  我们用dp数组记录下到第值为i的数字时,所能组成i的最少完美平方数
  

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
  / \
 15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

---

很标准的一题BFS，利用队列存储结点信息，按照标准的BFS思路层层遍历就可以了
思路：遍历完一层，队列push一个NULL作为分界符以合并结果

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> my_queue;
        vector<vector<int>> res;
        vector<int> tmp_res;
        TreeNode *tmp;

        if(!root)
            return res;
        
        my_queue.push(root);
        my_queue.push(NULL);

        while(!my_queue.empty()){
            while(my_queue.front()!=NULL){
                tmp = my_queue.front();
                tmp_res.push_back(tmp->val);
                if(tmp->left)
                    my_queue.push(tmp->left);
                if(tmp->right)
                    my_queue.push(tmp->right);
                my_queue.pop();
            }
            my_queue.pop();
            if(!my_queue.empty())
                my_queue.push(NULL);
            res.push_back(tmp_res);
            tmp_res.clear();
        }

        return res;
    }
};

01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

image.png

寻找离0最近的1，并把矩阵重新标记为它们之间的距离。

思路:把0元素位置全部入队，然后非0元素全部标记为MAX。然后pop队列，寻找队首元素（x）的四个方向，如果方向上的值 小于等于x+1的话（证明这个方向上的值是0），不做任何操作。反之，把这个方向上的值赋值为 x+1，并把这个值的位置入队。这样相当于对每个pop出来的位置，进行小范围的BFS

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      queue<vector<int>> nodes_queue;
      vector<vector<int>> directions={{-1,0},{1,0},{0,-1},{0,1}};//four directions
      int rows = matrix.size();
      int cols = matrix[0].size();

      vector<int> tmp_node;


      // redefine matrix
      for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            if(matrix[i][j]!=0)
                matrix[i][j] = INT_MAX;
            else if(matrix[i][j]==0)
                nodes_queue.push({i,j}); 
        }
      }

      while(!nodes_queue.empty()){
        tmp_node = nodes_queue.front();
        int x = tmp_node[0];
        int y = tmp_node[1];

        for(auto item:directions){
            int curr_x = x+item[0];
            int curr_y = y+item[1];
            if((curr_x<0 || curr_x>=rows || curr_y<0 || curr_y>=cols) || matrix[curr_x][curr_y]<=(matrix[x][y]+1))
                continue;
            matrix[curr_x][curr_y]=matrix[x][y]+1;
            nodes_queue.push({curr_x,curr_y});
        }
        nodes_queue.pop();
      }

      return matrix;

    }
};