leetcode网做题链接：200. 岛屿数量 - 力扣（LeetCode）

思路：

深度优先遍历DFS

目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。

dfs方法： 设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。

• 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
• 终止条件：
  • (i, j) 越过矩阵边界;
  • grid[i][j] == 0，代表此分支已越过岛屿边界。
• 搜索岛屿的同时，执行 grid[i][j] = ‘0’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
• 主循环：
  • 遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。

• 复杂度：所有的数遍历一遍，所以复杂度是O(N*M)

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        // 当前部分走过了，因此把当前部分置为0
        grid[i][j] = '0';
        // 依次看看上下左右是不是还有同属岛屿的其他部分
        // 若有，则依次遍历并置为0
        if (i > 0 && grid[i-1][j] == '1')
            dfs(grid, i-1, j);
        if (i < grid.size()-1 && grid[i+1][j] == '1')
            dfs(grid, i+1, j);
        if (j > 0 && grid[i][j-1] == '1')
            dfs(grid, i, j-1);
        if (j < grid[0].size()-1 && grid[i][j+1] == '1')
            dfs(grid, i, j+1);
    }
 
    int numIslands(vector<vector<char>>& grid) {
        // 分别记录行、列以及岛屿总数
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
        // 从第一行第一列开始，寻找有没有是'1'的位置，若有，则登岛遍历，岛屿数加1
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    dfs(grid, i, j);
                    ++cnt;
                }
            }
        }
        // 返回岛屿的总数
        return cnt;
    }
};

广度优先遍历 BFS

• 主循环和思路一类似，不同点是在于搜索某岛屿边界的方法不同。
• bfs 方法：
  • 借助一个队列queue，判断队列首部节点(i, j)是否未越界而且为1
    • 如果是则置（删除此岛屿），并将此节点上下左右节点(i+1,j),(i-1,j),(i,j+1),(i,j-1)加入队列
    • 如果不是则跳过此节点
  • 循环pop队列首节点，直到整个队列为空，此时已经遍历完此岛屿

class Solution {
public:
 
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
 
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                // 只要找到了一个为'1'的，那么登岛
                if (grid[i][j] == '1')
                {
                    // 当前找到的新岛屿，数量加1
                    ++cnt;
                    // 广度优先，那么需要借助队列来实现
                    queue<pair<int, int>> bfs_q;
                    // 把当前走过的地方置0
                    grid[i][j] = 0;
                    bfs_q.push({i, j});
                    // 只要队不空就循环
                    while (!bfs_q.empty())
                    {
                        // 取出队头元素，出队
                        auto cur = bfs_q.front();
                        bfs_q.pop();
                        // 判断队头元素的上下左右是否有岛屿的其他部分，有的话则入队并置0
                        if (cur.first > 0 && grid[cur.first-1][cur.second] == '1')
                        {
                            bfs_q.push({cur.first-1, cur.second});
                            grid[cur.first-1][cur.second] = 0;
                        }
                        if (cur.first < row-1 && grid[cur.first+1][cur.second] == '1')
                        {
                            bfs_q.push({cur.first+1, cur.second});
                            grid[cur.first+1][cur.second] = 0;
                        }
                        if (cur.second > 0 && grid[cur.first][cur.second-1] == '1')
                        {
                            bfs_q.push({cur.first, cur.second-1});
                            grid[cur.first][cur.second-1] = 0;
                        }
                        if (cur.second < col-1 && grid[cur.first][cur.second+1] == '1')
                        {
                            bfs_q.push({cur.first, cur.second+1});
                            grid[cur.first][cur.second+1] = 0;
                        }
                    }
                }
            }
        }
        return cnt;
    }
};

并查集

        是一种树型的数据结构，用于处理一些不相交的合并以及查询问题。

步骤：

• 遍历这个二维数组，将所有的1都认为是一个单独的集合
• 遍历这个二维数组，对于每一个1，只看它的左边和上边，如果发现有1，就做union操作（为甚只看左边和上边，因为右边和下边是对称的，而我们从左到右，从上到下遍历，所以不会重复和遗落）

class Solution {
public:
    int find(int idx)
    {
        // 若当前节点的父节点就是自己，那么只需要返回自己
        if (parent[idx] == idx) 
            return idx;
        // 路径压缩，只要idx节点的父节点不是整个集合的头节点，那么就把路径上每个节点都向集合的头结点
        parent[idx] = find(parent[idx]);
        // 返回idx的父节点（也是整个集合的头节点）
        return parent[idx];
    }
 
    void union_n (int idx_1, int idx_2)
    {
        int par_1 = find(idx_1);
        int par_2 = find(idx_2);
        // 若idx_1和idx_2的父节点是同一个，那就不做任何操作
        if (par_1 == par_2) 
            return;
        // 原本par_1和par_2分别是idx_1和idx_2的父节点，因此都指向自己
        // 这个赋值将par_1的父节点指向了par_2，完成了合并操作
        parent[par_1] = par_2;
        // 每当一块陆地拼进了岛屿，那么陆地数量自减
        --land_num;
    }
 
    int numIslands(vector<vector<char>>& grid) {
        // 输入的行与列
        int row = grid.size();
        int col = grid[0].size();
        // 初始化陆地数量以及数组
        land_num = 0;
        parent = vector<int> (row*col, -1);
        // 构建并查集
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                    ++land_num;
                // 初始化父亲节点都为自己
                parent[i*col + j] = i*col + j;
            }
        // 进行并查的过程
        for (int i = 0; i < row; ++i)
            for (int j = 0; j <col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    // 从左往右逐行遍历，若下方或者右方的节点也是陆地，那么就拼在一起
                    if (i + 1 < row && grid[i+1][j] == '1')
                        union_n(i*col+j, (i+1)*col+j);
                    if (j + 1 < col && grid[i][j+1] == '1')
                        union_n(i*col+j, i*col+j+1);
                }
            }  
        // 返回剩下的陆地数量（岛屿数量）
        return land_num;
    }
private:
    // 记录父节点以及陆地的数量
    vector<int> parent;
    int land_num;
};