图的遍历与泛洪算法

图的遍历与泛洪算法

深度优先遍历；广度优先遍历；泛洪算法（Flood Fill）。

概念

在图或二维网格上，DFS/BFS 遍历访问所有从起点可达的结点；Flood Fill（泛洪/填充）是典型应用：从某格出发，把与之四连通（或八连通）且同色/同类的格子全部标记。本叶子考的是「连通性、遍历顺序、visited 数组、邻接关系」，与 cspj.algo.dfs-bfs 相邻：后者更抽象，可含非图题的状态搜索；这里题面更常出现邻接矩阵/表、网格 g[i][j]、连通块计数。与 cspj.ds.graph 区分：数据结构叶子讲存储方式，本叶子讲怎么用遍历解决问题。

CSP-J 常考

• cspj-r1-2022 第 40–44 题：完善程序，Flood Fill 或图遍历的多处空位（2022 完善程序·洪水填充题组）。
• cspj-r1-2023 第 12 题：单选题，图的 DFS/BFS 或 Flood Fill 相关判断。

// Flood Fill：把与 (r,c) 四连通且值为 ch 的格子改为 '#'
void fill(char g[][], int r, int c, char ch) {
    if (r < 0 || c < 0 || !in(r,c) || g[r][c] != ch) return;
    g[r][c] = '#';
    fill(g, r+1, c, ch);
    fill(g, r-1, c, ch);
    fill(g, r, c+1, ch);
    fill(g, r, c-1, ch);
}

易错点

• 完善程序里递归 Flood Fill 边界判断写错，r,n 与 c,m 行列混淆。
• 把「遍历图」与「遍历树」等同：图要有 visited 防回边，树有时可不标记父节点但要看题意。
• 八连通与四连通搞混，阅读程序若数组偏移是 8 方向而题意是 4 方向，连通块大小会变。