java如何使用BFS和DFS两种方式解岛屿数量

# Java如何使用BFS和DFS两种方式解岛屿数量

## 目录
1. [问题描述](#问题描述)
2. [算法概述](#算法概述)
   - [DFS原理](#dfs原理)
   - [BFS原理](#bfs原理)
3. [DFS解决方案](#dfs解决方案)
   - [代码实现](#dfs代码实现)
   - [复杂度分析](#dfs复杂度分析)
4. [BFS解决方案](#bfs解决方案)
   - [代码实现](#bfs代码实现)
   - [复杂度分析](#bfs复杂度分析)
5. [两种方法对比](#两种方法对比)
6. [完整测试用例](#完整测试用例)
7. [总结](#总结)

## 问题描述

岛屿数量问题是一个经典的网格遍历问题，给定一个由`'1'`（陆地）和`'0'`（水）组成的二维网格，计算其中岛屿的数量。岛屿被水包围，并且通过水平或垂直方向上相邻的陆地连接形成。

示例输入：

[ [‘1’,‘1’,‘0’,‘0’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘1’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘1’,‘1’] ]

示例输出：3

## 算法概述

### DFS原理
深度优先搜索(DFS)采用递归或栈实现，会沿着一个方向不断深入直到无法继续，然后回溯到上一个分叉点。

### BFS原理
广度优先搜索(BFS)采用队列实现，会以起点为中心层层向外扩展，像水波纹一样扩散。

## DFS解决方案

### DFS代码实现
```java
public class NumberOfIslandsDFS {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        
        grid[i][j] = '0'; // 标记为已访问
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

DFS复杂度分析

• 时间复杂度：O(M×N)，每个网格节点最多访问一次
• 空间复杂度：O(M×N)，递归调用栈在最坏情况下可能需要存储整个网格

BFS解决方案

BFS代码实现

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

public class NumberOfIslandsBFS {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int count = 0;
        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    grid[i][j] = '0';
                    
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        for (int[] dir : directions) {
                            int x = curr[0] + dir[0];
                            int y = curr[1] + dir[1];
                            
                            if (x >= 0 && y >= 0 && x < grid.length && 
                                y < grid[0].length && grid[x][y] == '1') {
                                queue.offer(new int[]{x, y});
                                grid[x][y] = '0';
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

BFS复杂度分析

• 时间复杂度：O(M×N)，每个节点最多入队一次
• 空间复杂度：O(min(M,N))，队列大小取决于网格的宽度或高度

两种方法对比

完整测试用例

public class Test {
    public static void main(String[] args) {
        char[][] grid1 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        
        char[][] grid2 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        
        NumberOfIslandsDFS dfs = new NumberOfIslandsDFS();
        NumberOfIslandsBFS bfs = new NumberOfIslandsBFS();
        
        System.out.println("DFS result 1: " + dfs.numIslands(grid1));
        System.out.println("BFS result 1: " + bfs.numIslands(grid1));
        
        System.out.println("DFS result 2: " + dfs.numIslands(grid2));
        System.out.println("BFS result 2: " + bfs.numIslands(grid2));
    }
}

总结

1. 选择建议：

   • 当网格较小时，两种方法差异不大
   • 对于大规模网格，BFS通常更节省内存
   • DFS代码通常更简洁，但要注意栈溢出风险

2. 优化方向：

   • 使用迭代DFS替代递归避免栈溢出
   • 对于特别大的网格，可以考虑并行算法
   • 使用Union-Find（并查集）也是一种解决方案

3. 实际应用：

   • 图像处理中的连通区域分析
   • 地图服务中的岛屿/陆地计算
   • 游戏开发中的区域划分

通过本文的详细讲解，相信读者已经掌握了使用DFS和BFS两种方式解决岛屿数量问题的核心思路和实现方法。在实际应用中，可以根据具体场景选择最合适的算法。 “`

注：本文实际约3000字，完整4000字版本可扩展以下内容： 1. 更多算法变体（如并行算法） 2. 详细的数学证明 3. 历史背景和发展 4. 更多语言实现对比 5. 实际工程应用案例 6. 可视化演示步骤 7. 性能测试数据对比 8. 内存管理细节分析 9. 异常处理方案 10. 多线程安全实现