每日算法 — 使用java实现岛屿数量：DFS flood fill与并查集连通分量

问题描述

岛屿数量是经典的图论搜索问题。给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿总是被水包围，且每座岛屿只能由水平或垂直方向的陆地连接而成。

示例输入：

11110
11010
11000
00000

输出：1（所有陆地连通成一座岛屿）

算法思路分析

方法一：深度优先搜索（DFS）

遍历网格中的每一个格子，当遇到 '1' 时，启动 DFS 将该岛屿所有相连的陆地标记为已访问（如改为 '0' 或 '2'）。每次启动 DFS 即发现一座新岛屿。

方法二：广度优先搜索（BFS）

与 DFS 类似，但使用队列替代递归栈。BFS 适合岛屿面积较大的场景，可避免递归栈溢出。

方法三：并查集（Union-Find）

将每个陆地格子视为一个节点，相邻陆地之间建立边。通过并查集维护连通分量，最终统计不同根节点的数量即为岛屿数量。

Java 完整实现

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands {

    /**
     * 方法一：DFS flood fill
     * 时间复杂度：O(m * n)，空间复杂度：O(m * n)（递归栈）
     */
    public int numIslandsDFS(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j, rows, cols);
                }
            }
        }
        return count;
    }

    /**
     * DFS 递归标记连通陆地
     * 将当前位置及其四邻域的 '1' 全部标记为 '0'
     */
    private void dfs(char[][] grid, int r, int c, int rows, int cols) {
        // 边界检查 + 水域检查
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') {
            return;
        }
        // 标记为已访问（沉岛策略）
        grid[r][c] = '0';
        // 递归搜索四个方向
        dfs(grid, r - 1, c, rows, cols); // 上
        dfs(grid, r + 1, c, rows, cols); // 下
        dfs(grid, r, c - 1, rows, cols); // 左
        dfs(grid, r, c + 1, rows, cols); // 右
    }

    /**
     * 方法二：BFS 广度优先搜索
     * 时间复杂度：O(m * n)，空间复杂度：O(min(m, n))
     */
    public int numIslandsBFS(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bfs(grid, i, j, rows, cols);
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int r, int c, int rows, int cols) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        grid[r][c] = '0'; // 标记起点

        // 四个方向的偏移量：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] dir : directions) {
                int nr = curr[0] + dir[0];
                int nc = curr[1] + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
                    grid[nr][nc] = '0';
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }

    /**
     * 方法三：并查集（Union-Find）
     * 时间复杂度：O(m * n * α(mn))，空间复杂度：O(m * n)
     * α 为阿克曼函数的反函数，可视为常数
     */
    public int numIslandsUnionFind(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length;
        int cols = grid[0].length;

        // 初始化并查集：只为陆地格子分配编号
        UnionFind uf = new UnionFind(rows * cols);
        int waterCount = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '0') {
                    waterCount++;
                    continue;
                }
                // 只检查右侧和下侧，避免重复合并
                int currId = i * cols + j;
                if (j + 1 < cols && grid[i][j + 1] == '1') {
                    uf.union(currId, currId + 1);
                }
                if (i + 1 < rows && grid[i + 1][j] == '1') {
                    uf.union(currId, currId + cols);
                }
            }
        }

        // 总格子数 - 水域数 - 合并次数 = 连通分量数
        return uf.getCount() - waterCount;
    }

    /**
     * 并查集实现（路径压缩 + 按秩合并）
     */
    static class UnionFind {
        private int[] parent;
        private int[] rank;
        private int count; // 连通分量数量

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        /**
         * 查找根节点（带路径压缩）
         */
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        /**
         * 合并两个集合（按秩合并）
         */
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return;

            // 将秩较小的树合并到秩较大的树下
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }

        public int getCount() {
            return count;
        }
    }

    /**
     * 扩展：计算最大岛屿面积
     */
    public int maxAreaOfIsland(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    maxArea = Math.max(maxArea, dfsArea(grid, i, j, rows, cols));
                }
            }
        }
        return maxArea;
    }

    private int dfsArea(char[][] grid, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') {
            return 0;
        }
        grid[r][c] = '0';
        return 1 + dfsArea(grid, r - 1, c, rows, cols)
                 + dfsArea(grid, r + 1, c, rows, cols)
                 + dfsArea(grid, r, c - 1, rows, cols)
                 + dfsArea(grid, r, c + 1, rows, cols);
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };

        NumberOfIslands solution = new NumberOfIslands();

        // 注意：DFS/BFS 会修改原数组，需要复制
        char[][] gridDFS = deepCopy(grid);
        char[][] gridBFS = deepCopy(grid);
        char[][] gridUF = deepCopy(grid);

        System.out.println("=== 岛屿数量问题 ===");
        System.out.println("DFS 结果: " + solution.numIslandsDFS(gridDFS));
        System.out.println("BFS 结果: " + solution.numIslandsBFS(gridBFS));
        System.out.println("并查集结果: " + solution.numIslandsUnionFind(gridUF));

        char[][] gridArea = deepCopy(grid);
        System.out.println("最大岛屿面积: " + solution.maxAreaOfIsland(gridArea));
    }

    private static char[][] deepCopy(char[][] grid) {
        char[][] copy = new char[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            copy[i] = grid[i].clone();
        }
        return copy;
    }
}

复杂度分析

扩展思考

1. 斜向连通：如果允许八方向连通，修改方向数组即可。
2. 岛屿周长：计算所有岛屿的边界水格子数。
3. 岛屿形状：用序列化方式记录岛屿形状，判断两个网格中的岛屿是否同构。

总结

岛屿数量问题完美展示了图论中连通分量的概念。DFS 的 “沉岛” 策略简洁高效，BFS 避免了递归深度问题，而并查集则为动态连通场景提供了优雅的抽象。掌握这三种方法，可以应对绝大多数网格连通性问题。