博主罗勇军连通性问题是图论中的一个基本问题：找一张图中连通的点和边。很多图论题目或图论算法都需要判断连通性。判断连通性一般有三种方法：**BFS、DFS、并查集**。下面用一道例题介绍用BFS和DFS求解连通性问题。 *** 2018年蓝桥杯省赛真题 **全球变暖** 题目描述：有一张某海域 N×N 像素的照片，"."表示海洋、"#"表示陆地，如下图所示： ```cpp ....... .##.... .##.... ....##. ..####. ...###. ....... ``` 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。由于全球变暖导致海面上升，岛屿边缘一个像素的范围会被海水淹没。如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。例如上图中的海域未来会变成如下样子： ```cpp ....... ....... ....... ....... ....#.. ....... ....... ``` 请计算：照片中有多少岛屿会被完全淹没。输入：第一行包含一个整数N (1≤N≤1000)，以下N行N列代表一张海域照片。照片保证第 1 行、第 1 列、第N行、第N列的像素都是海洋。输出：一个整数表示答案。 *** 这是基本的连通性问题，计算步骤是：遍历一个连通块（找到这个连通块中所有的’#‘，并标记已经搜过，不用再搜）；再遍历下一个连通块…；遍历完所有连通块，统计有多少个连通块。连通性判断需要用暴力搜索解决：挨个搜连通块上的所有点，不遗漏一个；另外每个点只搜一次。这种简单的暴力搜索，用BFS和DFS都行，不仅很容易搜到所有点，而且每个点只搜一次，效率高。回到本题，什么岛屿不会被完全淹没？若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。用DFS或BFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。 **计算复杂度**：因为每个像素点只用搜一次且必须至少搜一次，共$N^2$个点，复杂度$O(N^2)$，不可能更好了。为了对比DFS和BFS，下面先用DFS实现，后面再用BFS实现。做题时，**一般用DFS判断连通性**，DFS比BFS编码少。 # 1. DFS求解连通性问题 DFS所有的像素点，若遇到’#‘，就继续DFS它周围的’#‘。把搜过的’#‘标记为已经搜过，不用再搜。统计那些没有高地的岛的数量，就是答案。搜索时应该判断是不是出了边界。不过，题目已经说“照片保证第1行、第1列、第N行、第N列的像素都是海洋”，那么就不用判断边界了，到了边界，发现是水，DFS会自动停止搜索。下面的代码，main()中每做一次DFS就是搜一个岛屿。代码中有两个重要变量。（1）flag。在一次DFS中，如果发现这个岛有高地，置flag=1。如果这个岛中没有高地，那么有flag=0，统计答案ans++。（2）vis[][]用于判断一个点是否被搜过。如果vis[][]==1，后面就不用重复搜了。代码第15行: ```cpp if(vis[nx][ny]==0 && mp[nx][ny]=='#') ``` 判断vis[nx][ny]==0。如果没有这个判断，那么很多点会重复进行DFS，导致超时。这是一种剪枝技术，叫作“记忆化搜索”。 ```cpp #include using namespace std; const int N = 1010; char mp[N][N]; //地图 int vis[N][N]={0}; //标记是否搜过 int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向 int flag; //用于标记这个岛中是否被完全淹没 void dfs(int x, int y){ vis[x][y] = 1; //标记这个'#'被搜过。注意为什么放在这里 if( mp[x][y+1]=='#' && mp[x][y-1]=='#' && mp[x+1][y]=='#' && mp[x-1][y]=='#' ) flag = 1; //上下左右都是陆地，这是一个高地，不会淹没 for(int i = 0; i < 4; i++){ //继续DFS周围的陆地 int nx = x + d[i][0], ny = y + d[i][1]; if(vis[nx][ny]==0 && mp[nx][ny]=='#') //注意为什么要判断vis[][] //继续DFS未搜过的陆地，目的是标记它们 dfs(nx,ny); } } int main(){ int n; cin >> n; for (int i = 0; i < n; i++) cin >> mp[i]; int ans = 0 ; for(int i = 1; i <= n; i++) //DFS所有像素点 for(int j = 1; j <= n; j++) if(mp[i][j]=='#' && vis[i][j]==0){ flag = 0; //假设这个岛被淹 dfs(i,j); //找这个岛中有没有高地，如果有,置flag=1 if(flag == 0) ans++; //这个岛被淹了，统计被淹没岛的数量 } cout<2. BFS求解连通性问题 BFS的思路比较简单。下面代码第34行，看到一个"#"后，就用BFS扩展它周围的"#"，所有和它相连的"#"属于一个岛。然后按前面DFS提到的方法：找高地，判断是否淹没。代码比DFS要复杂一点，因为用到了队列。这里直接用STL的queue，放进队列的是坐标点pair。 ```cpp #include using namespace std; const int N = 1010; char mp[N][N]; int vis[N][N]; int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向 int flag; void bfs(int x, int y) { queue> q; q.push({x, y}); vis[x][y] = 1; //标记这个'#'被搜过 while (q.size()) { pair t = q.front(); q.pop(); int tx = t.first, ty = t.second; if( mp[tx][ty+1]=='#' && mp[tx][ty-1]=='#' && mp[tx+1][ty]=='#' && mp[tx-1][ty]=='#' ) flag = 1; //上下左右都是陆地，不会淹没 for (int i = 0; i < 4; i++) { //扩展(tx,ty)的4个邻居 int nx = tx + d[i][0], ny = ty + d[i][1]; if(vis[nx][ny]==0 && mp[nx][ny]=='#'){ //把陆地放进队列 vis[nx][ny] = 1; //注意：这一句必不可少 q.push({nx, ny}); } } } } int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> mp[i]; int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (mp[i][j] == '#' && vis[i][j]==0) { flag = 0; bfs(i, j); if(flag == 0) ans++; //这个岛全部被淹，统计岛的数量 } cout << ans << endl; return 0; } ```