岛屿数问题Leetcode递归DFS和非递归BFS

Question

我试图使用递归 DFS 方法和非递归 BFS 方法来修复以下 leetcode 问题。两者都有效，但递归 DFS 快 3 毫秒，而非递归 BFS 快 6 毫秒。有人可以解释一下为什么 DFS 更快，并让我知道改进 BFS 代码的方法吗？

Leetcode问题描述：

200. 岛屿数量

给定一个 m x n 2D 二进制网格，它表示“1”（陆地）和“0”（水）的地图，返回岛屿的数量。

岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

示例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
Example 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
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '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); //can be replaced with callDFS
            }
        }
    }
    return count;
}

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);
}

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 方法将以非常相似的速度运行。

Answer 1

我预计 DFS 和 BFS 方法将以非常相似的速度运行。

实际上，由于一个人的运行速度是另一个人的两倍，因此他们的运行时间具有相同的数量级，“只是”相差 2 倍。

BFS 代码在每次“访问”单元时都会产生一些开销：

• 从队列中添加和轮询
• 坐标配对和取消配对

DFS 的开销主要由内部调用堆栈管理组成，预计这比显式队列实现更快。

但是我们可以尝试优化一下：

• 使用

  ArrayDeque

  代替

  LinkedList

• 将

  Pair<Integer, Integer>

  替换为

  Integer

  ，并将坐标与简单的公式组合成唯一的整数。
当您向队列中
• 添加

  单元格时，

  将

  grid[row][col]

  设置为0，而不是在从队列中轮询时执行此操作。这可以避免将同一单元多次放入队列，从而使队列更短。

这是更新后的

BFS

代码：

private static void callBFS(char[][] grid, int i, int j ) {
    int n = grid.length;
    int m = grid[0].length;
    java.util.Queue<Integer> myQueue = new ArrayDeque<>();

    grid[i][j] = '0';
    myQueue.add(i * m + j);

    while (!myQueue.isEmpty()) {
        int tempPair = myQueue.poll();
        int row = tempPair / m;
        int col = tempPair % m;
        if (row+1 < n && grid[row+1][col] == '1') {
            grid[row+1][col] = '0';
            myQueue.add(tempPair + m);
        }
        if (row > 0 && grid[row-1][col] == '1') {
            grid[row-1][col] = '0';
            myQueue.add(tempPair - m);
        }
        if (col > 0 && grid[row][col-1] == '1') {
            grid[row][col-1] = '0';
            myQueue.add(tempPair - 1);
        }
        if (col+1 < m && grid[row][col+1] == '1') {
            grid[row][col+1] = '0';
            myQueue.add(tempPair + 1);
        }
    }
}

尽管如此，队列开销仍然存在，使其比基于递归的 DFS 算法慢一些。