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