admin 管理员组

文章数量: 887007

深度优先搜索岛屿数量

首先回顾一下图的深度优先遍历(DFS)和广度优先遍历(BFS)算法分析

方法一：深度优先搜索

我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。



class Solution {
private:void dfs(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();  //行int nc = grid[0].size();  //列// 当前单元格grid[r][c] = '0'; //在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c); //上if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c); //下if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1); //左if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1); //右//当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。}public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1')//如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。{++num_islands;  //岛屿的数量dfs(grid, r, c); //深度优先搜索}}}return num_islands;}
};

复杂度分析
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

方法二：广度优先搜索

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row-1][col] == '1') {neighbors.push({row-1, col});grid[row-1][col] = '0';}if (row + 1 < nr && grid[row+1][col] == '1') {neighbors.push({row+1, col});grid[row+1][col] = '0';}if (col - 1 >= 0 && grid[row][col-1] == '1') {neighbors.push({row, col-1});grid[row][col-1] = '0';}if (col + 1 < nc && grid[row][col+1] == '1') {neighbors.push({row, col+1});grid[row][col+1] = '0';}}}}}return num_islands;}
};

时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(min(M, N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M, N)。

方法三：并查集

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。
最终岛屿的数量就是并查集中连通分量的数目。
下面的动画展示了整个算法。






class UnionFind {
public:UnionFind(vector<vector<char>>& grid) {count = 0;int m = grid.size();int n = grid[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {parent.push_back(i * n + j);++count;}else {parent.push_back(-1);}rank.push_back(0);}}}int find(int i) {if (parent[i] != i) {parent[i] = find(parent[i]);}return parent[i];}void unite(int x, int y) {int rootx = find(x);int rooty = find(y);if (rootx != rooty) {if (rank[rootx] < rank[rooty]) {swap(rootx, rooty);}parent[rooty] = rootx;if (rank[rootx] == rank[rooty]) rank[rootx] += 1;--count;}}int getCount() const {return count;}private:vector<int> parent;vector<int> rank;int count;
};class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (!nr) return 0;int nc = grid[0].size();UnionFind uf(grid);int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {grid[r][c] = '0';if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);}}}return uf.getCount();}
};

复杂度分析

时间复杂度：O(MN∗α(MN))，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 α(x) 的值不会超过 55，因此也可以看成是常数时间复杂度。

空间复杂度：O(MN)，这是并查集需要使用的空间。

参考

本文标签： 深度优先搜索岛屿数量

版权声明：本文标题：深度优先搜索岛屿数量 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732350822h1532997.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。