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

本文主要是介绍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<grid.length;i++) {
			 for(int j=0;j<grid[0].length;j++) {
				 area=Math.max(area, maxArea(i,j,grid));  //递归比较得到最大的岛屿面积area
			 }
		 }
		 return area;
	 }

	public static int maxArea(int x, int y,int[][] grid) {
		//确保节点合法防止数组越界且该节点为1即是陆地
		if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]==1) {
			grid[x][y]=0;   //将访问过的陆地置0，防止重复访问
			//返回该节点上下左右四个方向所有陆地面积
			return 1+maxArea(x+1, y, grid)+maxArea(x-1, y, grid)+
					maxArea(x, y-1, grid)+maxArea(x, y+1, grid);
		}else{
			return 0;
		}
	}

2.广度优先搜索

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

public static int maxAreaOfIsland(int[][] grid) {
		int area=0;
		for(int i=0;i<grid.length;i++) {
			for(int j=0;j<grid[0].length;j++) {
				if(grid[i][j]==1) {
					area=Math.max(area, bfs(grid,i,j));
				}
			}
		}
		return area;
	}
	
	public static int bfs(int grid[][],int i,int j) {
		Queue<int[]> queue=new LinkedList<int[]>();  //创建队列
		queue.offer(new int[] {i,j});  //向队列中添加位置数组作为起始节点
		grid[i][j]=0; //入队的节点（已访问）标为0
		int area=1;  //因为已有至少一块陆地，area初始值设为1	
		int[] 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&&nx<grid.length&&ny>0&&ny<grid[0].length&&grid[nx][ny]==1) {
					queue.offer(new int[] {nx,ny});
					grid[nx][ny]=0;
					area++;
				}
			}	
		}
		return area;
	}

这篇关于695.岛屿的最大面积（力扣）-JAVA-深度优先搜索和广度优先搜索详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！