LeetCode岛屿数量问题：递归DFS比非递归BFS更快的原因及优化方法

我用递归DFS和非递归BFS两种方法解决了LeetCode第200题「岛屿数量」，两种方法都能正确运行，但递归DFS耗时3ms，非递归BFS耗时6ms。原本预期两者速度接近，想了解DFS更快的原因，同时希望得到BFS代码的优化方案。

问题背景（LeetCode 200. 岛屿数量） #

给定一个由'1'（陆地）和'0'（水域）组成的m×n二维二进制网格grid，返回岛屿的数量。岛屿是由相邻陆地横向或纵向连接而成，且四周被水域包围，网格的四个边缘均被水域环绕。

示例1 #

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

示例2 #

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

约束条件 #

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 为 '0' 或 '1'

我的实现代码 #

public static int numIslands(char[][] grid) {
    int count = 0;

    for(int i=0; i<grid.length; i++){
        for(int j=0; j<grid[i].length; j++){
            if(grid[i][j]=='1'){
                count+=1;
                callBFS(grid, i, j); // 替换为callDFS即可切换方法
            }
        }
    }
    return count;
}

// 递归DFS实现
private static void callDFS(char[][] grid, int i, int j ) {
    if(i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0'){
        return;
    }
    grid[i][j]='0';

    callDFS(grid, i+1, j);
    callDFS(grid, i-1, j);
    callDFS(grid, i, j-1);
    callDFS(grid, i, j+1);
}

// 非递归BFS实现
private static void callBFS(char[][] grid, int i, int j ) {
    java.util.Queue<Pair<Integer, Integer>> myQueue = new LinkedList<>();

    Pair<Integer, Integer> initialPair = new Pair<>(i, j);
    myQueue.add(initialPair);

    while(!myQueue.isEmpty()){
        Pair<Integer, Integer> tempPair = myQueue.poll();
        int row = tempPair.getKey();
        int col = tempPair.getValue();
        if(grid[tempPair.getKey()][tempPair.getValue()]=='1'){
            grid[tempPair.getKey()][tempPair.getValue()]='0';
            if(row+1<grid.length && grid[row+1][col]=='1'){
                myQueue.add(new Pair<>(row+1, col));
            }
            if(row-1>=0 && grid[row-1][col]=='1'){
                myQueue.add(new Pair<>(row-1, col));
            }
            if(col-1>=0 && grid[row][col-1]=='1'){
                myQueue.add(new Pair<>(row, col-1));
            }
            if(col+1<grid[row].length && grid[row][col+1]=='1'){
                myQueue.add(new Pair<>(row, col+1));
            }
        }
    }
}

问题解答 #

一、递归DFS比BFS更快的原因 #

1. 对象创建与队列开销
   你的BFS实现中频繁创建Pair对象，且使用LinkedList作为队列——LinkedList是链表结构，每次入队出队都要处理节点的指针操作，开销远大于递归调用的栈帧开销。JVM对栈帧的管理非常高效，递归调用的栈帧复用和销毁成本很低。

2. 内存局部性差异
   DFS是深度优先遍历，会连续访问同一方向的相邻节点（比如一直向下遍历），这些节点在二维数组的内存中是连续存储的，能更好地利用CPU缓存，缓存命中率更高；而BFS是广度扩散，节点分布更分散，缓存命中率低，会导致更多的内存访问延迟。

3. 重复入队问题
   当前BFS是在取出节点后才标记为'0'，这会导致同一个节点可能被多个相邻节点重复加入队列，增加了不必要的队列操作和节点处理次数。而DFS在进入节点时立刻标记，从根源避免了重复处理。

二、BFS代码优化方案 #

针对上述问题，可从以下几点优化BFS代码：

• 用ArrayDeque代替LinkedList：ArrayDeque基于数组实现，入队出队操作的时间复杂度更低，且内存局部性更好。
• 取消Pair类：用int[]代替Pair，减少对象创建开销。
• 入队前标记节点：在将节点加入队列前就标记为'0'，避免重复入队。
• 用方向数组简化遍历代码：提升可读性和代码简洁度。

优化后的BFS代码：

private static void callBFS(char[][] grid, int i, int j ) {
    // 使用ArrayDeque存储int数组，替代LinkedList+Pair
    java.util.Queue<int[]> queue = new java.util.ArrayDeque<>();
    // 入队前先标记为0，避免重复入队
    grid[i][j] = '0';
    queue.add(new int[]{i, j});

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

    while(!queue.isEmpty()){
        int[] curr = queue.poll();
        int row = curr[0];
        int col = curr[1];

        // 遍历四个方向
        for(int[] dir : dirs){
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            // 检查边界和是否为陆地
            if(newRow >=0 && newRow < grid.length && newCol >=0 && newCol < grid[newRow].length && grid[newRow][newCol] == '1'){
                grid[newRow][newCol] = '0';
                queue.add(new int[]{newRow, newCol});
            }
        }
    }
}

优化说明：

• 用int[]替代Pair，减少了对象创建的开销；
• 入队前就标记节点为'0'，彻底避免了重复入队；
• 使用ArrayDeque作为队列，比LinkedList更高效；
• 用方向数组简化四个方向的遍历代码，可读性和性能都有提升。

内容的提问来源于stack exchange，提问作者Alex Sorin