网格图 DFS 与 BFS

ZaynPei Lv6
  2025-10-09 22:00 2025-10-09 22:00 Created   2025-11-04 16:06:41 2025-11-04 16:06:41 Updated      2.6k Words  11 Mins

网格图 (Grid Graph) 是一种特殊的图结构，节点排列成二维矩阵的形式，每个节点与其上下左右（有时包括对角线方向）的邻居节点相连。

它本质上是图论问题，但比图论更“友好”，因为它是一个“隐式图”。你不需要自己构建邻接表，一个 (r, c) 单元格的邻居就是 (r+1, c), (r-1, c) 等。

这一章的核心是考察你对两种最基本图遍历算法的理解和应用： - DFS (深度优先搜索) - BFS (广度优先搜索) 选择 DFS 还是 BFS 不是随意的，而是由题目的核心诉求决定的。

  • 选择 DFS (深度优先搜索)
    • “不撞南墙不回头”。它会沿着一个方向“走到底”，然后再回溯。
    • 机制：依赖递归或者栈（函数调用栈）。
    • 何时使用？当题目问的是“连通性”、“有多少块”、“这一块有多大”、“能不能到达”时。
      • (岛屿数量)：DFS 非常适合“淹没”一个连通块。
    • 优点：代码通常更简洁（递归天然处理了回溯）。
  • 选择 BFS (广度优先搜索)
    • “一圈一圈往外扩”。像水波纹一样，先访问所有距离为 1 的，再访问所有距离为 2 的…
    • 机制：依赖队列 (Queue)。
    • 何时使用？当题目问的是“最短”路径、“最少”步数、“最快”时间时（在无权图中）。
      • (01 矩阵)：求每个点到最近的 0 的距离。
    • 优点：天然地保证找到的路径是最短的。

网格图 DFS (连通性问题)

这是网格图的基础, 适用于解决“连通性”问题，比如“岛屿数量”、“最大岛屿面积”、“是否存在路径”等。

例题分析：200. 岛屿数量 ：给你一个 m x n 的、由 ‘1’（陆地）和 ‘0’（水）组成的网格图，返回岛屿的数量。

解题思路 (DFS)： - 主函数：写一个双层 for 循环遍历所有单元格 (r, c)。 - int island_count = 0; - 循环的核心逻辑： - if (grid[r][c] == ‘1’)： - 解释：我们找到了一个新岛屿的“一角”，它还没有被访问过。 - island_count++; （答案加 1） - dfs(grid, r, c); （调用 DFS，把与 (r, c) 相连的整座岛全部“淹没”, 即标记为’0’） - return island_count; 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    if (m == 0) return 0; // 处理空网格
    int n = grid[0].size();
    
    int sum = 0;
    // (步骤说明)：遍历网格中的每一个单元格
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 如果找到一块陆地 ('1')
            if (grid[i][j] == '1') {
                
                sum++;   // 我们发现了一个新岛屿，计数器加 1
                // (步骤说明)：调用 DFS 将这个岛屿上的所有 '1'
                // 全部“淹没” (改成 '0')，这样它们就不会被重复计算
                dfs(grid, i, j);
            }
        }
    }
    return sum;
}
// 辅助函数：深度优先搜索 (DFS), 用于“淹没”与 (r, c) 相连的所有陆地
void dfs(vector<vector<char>>& grid, int r, int c) {
    int m = grid.size();
    int n = grid[0].size();

    // (步骤说明)：Base Case 1: 检查是否越界
    if (r < 0 || r >= m || c < 0 || c >= n) {
        return;
    }

    // (步骤说明)：Base Case 2: 检查是否为水或已访问 (已沉没)
    if (grid[r][c] != '1') {
        return;
    }

    // (步骤说明)：淹没当前陆地格
    // 也可以使用其他标记方式，比如 bool visited[m][n] 数组 来标记已访问
    grid[r][c] = '0'; 
    // (步骤说明)：向四个方向递归，淹没所有相连的陆地
    dfs(grid, r + 1, c); // 下
    dfs(grid, r - 1, c); // 上
    dfs(grid, r, c + 1); // 右
    dfs(grid, r, c - 1); // 左
}

网格图 BFS (最短路径问题)

核心思想： - 队列 (Queue)：std::queue<std::pair<int, int>> q; 存储待访问的坐标 (r, c)。 - 层级 (Level)：BFS 的关键是“一层一层”地遍历。你需要一个 while (!q.empty()) 循环处理该位置可能的所有邻居，并在内部再用一个 for 循环来处理当前层的所有节点。 - 访问数组 (Visited Array)：必须要有, 而且BFS 的 visited 标记必须在入队 (push) 时就标记

例如, 二进制矩阵中最短路径问题 (LC 1091) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0]==1) return -1;   
        int n = grid.size();
        if(n==1) return 1;  

        queue<vector<int>> q;  // 队列存储当前坐标和步数
        vector<vector<bool>> isvisted(n, vector<bool>(n, false));    // 访问数组
        
        q.push({0,0,1});
        isvisted[0][0] = true;
        vector<vector<int>> dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};  // 将八个方向都考虑进去, 且写成数组方便遍历

        while(!q.empty()){ 
            vector<int> curr = q.front();  
            q.pop();
            int r = curr[0];
            int c = curr[1];
            int step = curr[2];

            if(r==n-1&&c==n-1) return step;  // 到达终点, 返回步数
            
            for(auto& dir:dirs){  // 遍历八个方向
                int next_r = r+dir[0];
                int next_c = c+dir[1];
                if(next_r<0||next_c<0||next_r>=n||next_c>=n
                        ||isvisted[next_r][next_c]||grid[next_r][next_c]==1){
                    continue;
                }  // 越界或已访问或障碍, 直接跳过
                q.push({next_r,next_c,step+1});  // 入队列, 步数加1, 下一轮会处理
                isvisted[next_r][next_c] = true; 
            }
        }
        return -1;
    }
};
再例如, 腐烂的橘子 (LC 994) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    // 1. 初始化：队列、方向数组、统计新鲜橘子
    queue<pair<int, int>> q;    // BFS 队列, 主要保存坐标信息
    vector<vector<int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int fresh_count = 0; // 统计新鲜橘子数量
    int minutes = 0;     // 记录分钟数，即 BFS 的层数

    // 2. 初始扫描：入队所有腐烂橘子(源头)，统计所有新鲜橘子
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                q.push({i, j});
            } else if (grid[i][j] == 1) {
                fresh_count++;
            }
        }
    }

    // 3. 边缘情况处理：如果一开始就没有新鲜橘子
    if (fresh_count == 0) {
        return 0;
    }

    // 4. BFS 主循环 (按层遍历)
    while (!q.empty()) {
        // 核心：锁定当前层级的节点数量
        int size = q.size(); 

        // 5. 处理当前层的所有节点
        for (int i = 0; i < size; i++) {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();

            // 探索4个方向
            for (auto& dir : dirs) {
                int r_new = r + dir[0];
                int c_new = c + dir[1];

                // 检查新坐标是否有效 且 是否为新鲜橘子
                if (r_new >= 0 && r_new < m && c_new >= 0 && c_new < n && grid[r_new][c_new] == 1) {
                    // 腐烂它
                    grid[r_new][c_new] = 2;
                    q.push({r_new, c_new}); // 加入队列，供下一分钟处理
                    
                    // 更新新鲜橘子计数
                    fresh_count--; 
                }
            }
        }
        
        // 6. 关键：更新时间
        // 如果队列非空(说明还有下一层)，则时间+1
        if (!q.empty()) {
            minutes++;
        }
    }

    // 7. 最终结果判断 (使用优化后的计数)
    return (fresh_count == 0) ? minutes : -1;
}

思考题

BFS 队列 vs. DFS 递归栈的最大空间？两者最坏情况都是 O(m × n)。

  • BFS 队列：当图是一个“稠密”的棋盘格时，从角落出发，队列在中间某一层会包含近 O(m × n) 个节点。
  • DFS 栈：当图的构造是一个“蛇形”路径，它填满了所有单元格。DFS 会从头一口气走到尾，递归深度（栈空间）为 O(m × n)。

如何构造让 DFS 递归深度最大？蛇形/螺旋形路径。起点 (0,0)：构造一个“贪吃蛇”路径，例如： 

1
2
3
4
5
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 1 1 1
1 0 0 0 0
(假设 1 是路径，0 是墙)。DFS 会从 (0,0) 沿着 1 一直走到 (4,0)，深度 O(mn)。起点 (i,j)：以 (i,j) 为起点，构造一个螺旋形或蛇形路径占满整个图。

一般图

有时候题目并没有给出网格图，而是给出一些非图的信息, 你需要自己构造图的邻接关系, 然后再用 DFS 或 BFS 来遍历。

常见的建图方式有： - 邻接矩阵 (Adjacency Matrix): 二维数组表示节点间的连接关系, 例如 A[i][j] = 1 表示节点 i 和 j 之间有边相连。 - 对于无向图, 矩阵是对称的; 而对于有向图, A[i][j] = 1 表示从 i 指向 j 有一条边。 - 邻接表 (Adjacency List): 每个节点维护一个链表或数组，存储所有相邻节点。 - 对于无向图, 如果节点 i 和 j 相连, 那么 j 会出现在 i 的邻接表中, 同时 i 也会出现在 j 的邻接表中。 - 对于有向图, 只有 j 会出现在 i 的邻接表中。 - 入度数组往往和邻接表一起使用, 用于记录每个节点的入度 (有多少条边指向它)。这在拓扑排序等算法中非常有用。

例如, LC 207. 课程表: 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    
    // 1. 初始化邻接表和入度数组
    // 邻接表 adj[bi] 存储所有以 bi 为先修课的课程 ai
    vector<vector<int>> adj(numCourses);    // 在我之后学的课程
    // indegree[ai] 存储课程 ai 有多少门先修课
    vector<int> indegree(numCourses, 0);    // 在我之前必须学的课程数

    // 遍历所有先修关系, 从所给的条件中构建邻接表和入度数组
    for (const auto& pre : prerequisites) {
        int course = pre[0];   // 课程 ai
        int prereq = pre[1];   // 课程 bi
        
        // 建立一条从 bi 到 ai 的边
        adj[prereq].push_back(course); 
        
        // 课程 ai 的入度（先修课数量）加 1
        indegree[course]++;
    }

    // 2. 初始化队列，将所有入度为 0 的节点（课程）入队
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0; // 记录已修完的课程数量

    // 3. 执行 BFS
    while (!q.empty()) {
        // 从队列中取出一门课，代表我们“修完了”这门课
        int course = q.front();
        q.pop();
        count++; // 修完的课程数 +1

        // 遍历所有以 'course' 为先修课的后续课程 'nextCourse'
        for (int nextCourse : adj[course]) {
            // 'nextCourse' 的一门先修课 'course' 已经修完
            // 因此 'nextCourse' 的入度减 1
            indegree[nextCourse]--;

            // 检查：如果 'nextCourse' 的所有先修课都已修完（入度变为 0）
            if (indegree[nextCourse] == 0) {
                // 那么 'nextCourse' 现在可以学习了，将其入队
                q.push(nextCourse);
            }
        }
    }

    // 4. 判断结果
    // 如果修完的课程总数等于总课程数，说明没有环，可以完成
    // 否则，说明存在环，无法完成
    return count == numCourses;
}

On this page
网格图 DFS 与 BFS
  1. 网格图 DFS (连通性问题)
  2. 网格图 BFS (最短路径问题)
  3. 思考题
  4. 一般图