理解广度优先搜索(BFS)！

BFS：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

BFS：

• BFS类似于水波纹的扩散，在求解一些最短路径，最优值问题的时候效率很高。
• BFS为了遍历，需要保存所有的状态，对空间来说是一个巨大的消耗。（因为通常是无法递归实现的
• 结合题目与代码复习与分享：

• class Solution {
      private int[] dir=new int[]{-1,0,1,0,-1};//方向
      private int res=0;//目标
  
      public int shortestBridge(int[][] grid) {
      // 1. 先 dfs 将找到的第一座桥的值全部赋值为2，并将第一座桥旁边的 0 全部插入队列中
      // 2. 再 while 循环判断队列是否为空，循环体里会判断是否发现了第二座桥；
      Queue<int[]>queue=new LinkedList<>();//放第一座桥的0的队列
      //先dfs，将第一座桥设置为2
      boolean dfsFlag=false;
      for(int i=0;i<grid.length;i++){//外层是行长度进行循环
          if(dfsFlag){//为true，就结束循环
              break;
          }
          for(int j=0;j<grid[0].length;j++){//内层是列数进行循环
          if(grid[i][j]==1){//如果这个位置是1，就添加进dfs，判断是否为第一个岛屿的1
              dfs(grid,queue,i,j,grid.length,grid[0].length);
              dfsFlag=true;//当第一个岛屿的所以1找到后，将dfsFlag设置为true，从而进行下一步的最短距离寻找
              break;
          }
  
          }
      }
      //bfs，进行完第一个岛屿的寻找，就开始第二个岛屿的最近寻找，遍历时将0赋值为2
      while(!queue.isEmpty()){//队列不为空
      res++;//记录队列长度？
      int queueSize=queue.size();
      while(queueSize-->0){
          int[]root=queue.poll();
          for(int i=0;i<dir.length-1;i++){
              int x1=root[0]+dir[i];//新的x方向
              int y1=root[1]+dir[i+1];//新的y方向
              if(x1>=0&&x1<grid.length&&y1>=0&&y1<grid[0].length){
                  if(grid[x1][y1]==1){
                      return res;
                  }else if(grid[x1][y1]==2){
                      continue;
                  }
                  grid[x1][y1]=2;
                  queue.add(new int[]{x1,y1});
              }
          }
      }
      
      }
      return res;
      }
      private void dfs (int[][]grid,Queue<int[]>queue,int x,int y,int n,int m){
           // 插入所有为 0 的值的坐标到队列中
           // 为 1 的值就改变为 2 并且继续遍历四个方向
             // 为 2 的值就直接退出
             if (x < 0 || x == n || y < 0 || y == m || grid[x][y] == 2) {
              return;
          }
             if(grid[x][y]==0){//说明是到第二个岛屿的路径，添加到队列中，结束这次递归
                 queue.add(new int[]{x,y});
                 return;
             }
             grid[x][y]=2;//都不满足上面的就设置为2
             for(int i=0;i<dir.length-1;i++){//设置方向，寻找第一个岛屿的其他地方
                 int x1=x+dir[i];
                 int y1=y+dir[i+1];
                 dfs(grid,queue,x1,y1,n,m);//等价表达式
             }
      }
  
      }