LeetCode封闭岛屿问题：BFS超时DFS正常的原因解析

在解决LeetCode「Number of Closed Islands」问题时，出现了BFS解法超时但DFS解法正常运行的情况，此前仅得知“队列带来额外开销”的说法，现具体分析原因：

核心问题：你提供的BFS代码与当前问题不匹配 #

你贴出的BFS代码是另一道题「连通网络的操作次数（makeConnected）」的实现，完全没有针对「封闭岛屿数量」问题的逻辑（比如未处理二维网格、未排除边界岛屿等），这是导致超时或运行错误的直接原因。

假设使用正确的BFS代码，仍可能超时的具体原因 #

如果是针对该问题的正确BFS实现，超时可能来自以下几点：

1. 队列的缓存局部性劣势 #

DFS使用的递归栈是线程栈的连续内存区域，缓存命中率更高；而BFS的队列（如std::queue）通常基于堆内存分配，节点地址分散，缓存访问效率较低，在大规模网格下会累积性能差距。

2. 未及时标记访问状态导致重复入队 #

如果BFS中弹出节点时才标记已访问（而非入队时就标记），会导致同一个节点被多个邻居重复入队。例如节点A的两个邻居B、C，当处理A时，B未被标记，会被入队；后续处理其他节点时，C也会把未标记的B再次入队，造成队列中存在大量重复元素，额外增加处理开销。而DFS在进入节点时就标记为已访问，从根源避免了重复处理。

3. 数据结构的额外开销 #

如果BFS实现中使用了unordered_map这类哈希结构存储邻接关系，哈希查找、链表遍历的开销远高于DFS直接操作二维数组的索引访问，这也是性能差距的来源之一。

针对该问题的正确BFS示例 #

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int count = 0;
        // 先淹没边界的岛屿
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) bfs(grid, i, 0);
            if (grid[i][n-1] == 0) bfs(grid, i, n-1);
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 0) bfs(grid, 0, j);
            if (grid[m-1][j] == 0) bfs(grid, m-1, j);
        }
        // 统计封闭岛屿
        for (int i = 1; i < m-1; ++i) {
            for (int j = 1; j < n-1; ++j) {
                if (grid[i][j] == 0) {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

private:
    void bfs(vector<vector<int>>& grid, int row, int col) {
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> q;
        q.push({row, col});
        grid[row][col] = 1; // 入队时立即标记已访问
        // 四个方向
        vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            for (auto& dir : dirs) {
                int r = curr.first + dir.first;
                int c = curr.second + dir.second;
                if (r >= 0 && r < m && c >=0 && c < n && grid[r][c] == 0) {
                    grid[r][c] = 1; // 入队前标记，避免重复入队
                    q.push({r, c});
                }
            }
        }
    }
};

内容的提问来源于stack exchange，提问作者Mohak Gupta