LeetCode 200 Number of Islands：BFS/DFS 連通分量檢測完整對比

問題描述

同 ID 4430，此處提供 Java BFS/DFS 兩種實現對比，並分析層間訪問控制技巧。

BFS 實現（推薦：無遞歸棧溢出風險）

class Pair { int x, y; Pair(int x, int y) { this.x = x; this.y = y; } }

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int R = grid.length, C = grid[0].length;
    int ans = 0;
    
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (grid[i][j] == '1') {
                ++ans;
                Queue q = new LinkedList<>();
                q.offer(new Pair(i, j));
                grid[i][j] = '*';  // 入隊即標記，防止同層重複入隊
                
                while (!q.isEmpty()) {
                    Pair p = q.poll();
                    int[] dr = {1,-1,0,0}, dc = {0,0,1,-1};
                    for (int k = 0; k < 4; ++k) {
                        int nr = p.x + dr[k], nc = p.y + dc[k];
                        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1') {
                            grid[nr][nc] = '*';  // 關鍵：入隊前標記！
                            q.offer(new Pair(nr, nc));
                        }
                    }
                }
            }
        }
    }
    return ans;
}

關鍵優化：入隊即標記

在 BFS 中，發現鄰居為 '1' 時立即標記為 '*' 再入隊，而非出隊時標記。這防止了同一層的不同節點重複將同一鄰居加入隊列，顯著減少隊列大小和重複處理。

DFS 實現（代碼簡潔，但大數據可能棧溢出）

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int R = grid.length, C = grid[0].length;
    int ans = 0;
    
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (grid[i][j] == '1') {
                ++ans;
                dfs(grid, i, j, R, C);
            }
    return ans;
}

void dfs(char[][] grid, int r, int c, int R, int C) {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfs(grid, r+1, c, R, C);
    dfs(grid, r-1, c, R, C);
    dfs(grid, r, c+1, R, C);
    dfs(grid, r, c-1, R, C);
}

性能對比

工程選型建議

• 面試/競賽小數據：DFS 代碼最短、寫得最快
• 生產環境/大數據/未知規模：BFS 更安全、性能更穩定
• 並行化需求：BFS 天然適合層級並行