图论问题建模和floodfill算法

目录

引入：leetcode695.岛屿的最大面积

分析与转换

一维二维转换

四联通

完整代码解答： 

1）显示的创建图解决问题的代码

2）不显示的创建图解决此问题的代码

floodfill算法

定义

---

引入：leetcode695.岛屿的最大面积

分析与转换：

在题目中0是海水，1是陆地。在我们自己设定的图中假设蓝色是海水，红色是陆地。且每一个小格子都是一个顶点，若某个红色顶点上下左右方向有另外的红色顶点与它相邻，则在它俩中间连接一条边证明其一同构成了一个岛屿，也就是同属于一个连通分量。这样，我们就把这道题转换成了一个图论的问题。我们要求的问题也就转换成了找出包含顶点最多的连通分量，顶点个数也就是面积的最大值。

一维二维转换：

我们还可以通过数学公式将二维和一维相互转换。注意一维是从0开始计数， 二维是从1开始计数。

四联通：

我们需要搜索一个红色顶点的上下左右的顶点是否还是陆地，那么如何搜索呢？这就涉及到了四联通的概念。我们可以设立一个二维数组，里面的四个元素代表了相较于本顶点而言，它的行列坐标的位移，也就是表示它的上下左右各移动一个单位的四个坐标。值得注意的是，我们现在的坐标系不是我们熟知的数学坐标系，而是我们计算机一般使用的屏幕坐标系，我们可以理解成二维数组索引所在的坐标系。

d循环四次代表上下左右四个方向。 

 

 

完整代码解答： 

1）显示的创建图解决问题的代码

import java.util.HashSet;class Solution {private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C;//行数列数private int[][] grid;private HashSet<Integer>[] G;//图的邻接表的表示private boolean[] visited;public int maxAreaOfIsland(int[][] grid){if(grid == null) return 0;R = grid.length;if(R == 0) return 0;C = grid[0].length;if(C == 0) return 0;this.grid = grid;G = constructGraph();//进行建图操作int res = 0;visited = new boolean[G.length];for(int v = 0; v < G.length; v ++){int x = v / C, y = v % C;if(grid[x][y] == 1 && !visited[v])//如果v没被遍历过就是证明找到了一个新的岛屿，即一个新的连通分量。res = Math.max(res, dfs(v));}return res;}private int dfs(int v){visited[v] = true;int res = 1;//1是这是深度优先遍历v这个顶点for(int w: G[v])if(!visited[w])res += dfs(w);return res;}private HashSet<Integer>[] constructGraph(){HashSet<Integer>[] g = new HashSet[R * C];//开辟空间for(int i = 0; i < g.length; i ++)g[i] = new HashSet<>();for(int v = 0; v < g.length; v ++){int x = v / C, y = v % C;//转换成二维坐标if(grid[x][y] == 1){//只有它本身是陆地才去判断它四周是否有其他陆地与之相连for(int d = 0; d < 4; d ++){int nextx = x + dirs[d][0];int nexty = y + dirs[d][1];if(inArea(nextx, nexty) && grid[nextx][nexty] == 1) {//判断nextx和nexty是否合法（是否在网格范围中）int next = nextx * C + nexty;//转为一维索引g[v].add(next);//添加一条边g[next].add(v);}}}}return g;}private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}public static void main(String[] args){int[][] grid = {{0, 1}};System.out.println((new Solution()).maxAreaOfIsland(grid));}
}

2）不显示的创建图解决此问题的代码

class Solution {private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};private int R, C;private int[][] grid;private boolean[][] visited;public int maxAreaOfIsland(int[][] grid){if(grid == null) return 0;R = grid.length;if(R == 0) return 0;C = grid[0].length;if(C == 0) return 0;this.grid = grid;visited = new boolean[R][C];int res = 0;for(int i = 0; i < R; i ++)//二重循环遍历每一个顶点for(int j = 0; j < C; j ++)if(grid[i][j] == 1 && !visited[i][j])res = Math.max(res, dfs(i, j));return res;}private int dfs(int x, int y){visited[x][y] = true;int res = 1;for(int d = 0; d < 4; d ++){int nextx = x + dirs[d][0], nexty = y + dirs[d][1];if(inArea(nextx, nexty) && grid[nextx][nexty] == 1 && !visited[nextx][nexty])res += dfs(nextx, nexty);}return res;}private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}

floodfill算法

定义：

floodfill算法是一种图像处理算法，用于填充连通区域。该算法从一个起始点开始，将所有与该点相邻且颜色相同的像素点都标记为同一区域，并继续递归处理该区域的相邻像素点，直到所有相邻像素点都被标记为该区域。该算法通常用于图像处理、计算机图形学等领域中的填充操作，例如对图像中的某个区域进行颜色填充、图形的边界检测等。