695.岛屿的最大面积（力扣）-JAVA-深度优先搜索和广度优先搜索详解

一.题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

二.深度优先搜索和广度优先搜索详解 1.深度优先搜索

首先我们了解一下深度优先搜索，即从一个头结点开始，按一定的数据结构访问与头结点相连的下一个节点，再从下一个节点开始访问与当前节点相连的一个节点，循环往复，直到访问的当前节点没有下一个相连节点，开始回溯回当前节点的上一个节点，再以上一个节点为起始节点的前提下重复访问操作，不断回溯直到所有节点都被访问。
注意：访问过一个陆地节点后，一定要将访问过的节点置0，否则因为遍历地图每一块即将每一块都当做一次起始节点，会重复计算陆地面积
我们在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。

//遍历地图每一块 public static int maxAreaOfIsland(int[][] grid) { int area=0; //初始面积设为0 //访问每一格，以每一格都作为一次起始节点，往上下左右四个方向访问，四个方向所有连通的节点为1的总和即为该小岛屿的面积 for(int i=0;i=0&&x=0&&y

2.广度优先搜索

广度优先搜索简单理解就是，从起始节点开始，先将与起始节点相连所有节点入队列，然后取出队首节点，将该节点相连所有未访问节点加入队尾，再取出当前队首节点，循环往复直到队列为空，即所有节点都被访问过了。
访问起始土地，并将接下来想要遍历的土地（即与起始土地四个方向相连的土地）添加到队尾，每次从队首取出土地，就实现了广度优先搜索算法。

public static int maxAreaOfIsland(int[][] grid) {int area=0;for(int i=0;i queue=new linkedList(); //创建队列queue.offer(new int[] {i,j}); //向队列中添加位置数组作为起始节点grid[i][j]=0; //入队的节点（已访问）标为0int area=1; //因为已有至少一块陆地，area初始值设为1int[] queuei= {0,0,1,-1};int[] queuej= {1,-1,0,0};while(!queue.isEmpty()) {int[] tem=queue.poll(); //队首元素出队列int x=tem[0],y=tem[1]; //起始节点位置//把与{x,y}节点相连的所有陆地节点加入队尾for(int k=0;k<4;k++) {int nx=x+queuei[k],ny=y+queuej[k];if(nx>0&&nx0&&ny