LeetCode 图-岛屿问题

图

图的基本知识
- 基本概念
- - 图的类型
  - 相关术语
- 图的存储
LeetCode 相关题目
- 岛屿问题
- - 岛屿的最大面积
  - 岛屿的周长

图的基本知识

基本概念

图的类型

无向图
有向图
加权图

图的存储

邻接矩阵存储：是用一个二维数据数组(矩阵)存储图中顶点间的邻接关系。假设图G=(V, E)有n个顶点，那么邻接矩阵就是n*n的方阵。

以有权图为例：
在这里插入图片描述

邻接表：对于每个图的顶点v，将所有邻接于顶点v的顶点链成一个单链表（边表）。
以有权图为例：

LeetCode 相关题目

岛屿问题

我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的。而今天讨论的 DFS 问题，是在一种「网格」结构中进行的。岛屿问题是这类网格 DFS 问题的典型代表。

网格类问题的 DFS 遍历方法：

网格问题是由 m * n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。
岛屿问题每个格子中的数字可能是 0 或者 1。0 看成海洋，1 看成陆地，这样相邻的陆地就连接成一个岛屿。在这样一个设定下，就出现了各种岛屿问题的变种，包括岛屿的数量、面积、周长等。

二叉树 DFS 遍历一般是这样的：

void dfs(TreeNode* root) {
	// base case
	if (root == nullptr) return;
	// visit adjacent node
	dfs(root->left);
	dfs(root->right);
}

其中最关键的是处理好base case 的判断，以及访问相邻节点。在网格问题中，相邻节点就是上下左右四个格子，base case 就是数组下标越界的情况。
于是可以写出网格问题 dfs 遍历的代码：

void dfs(vector<vector<int>>& grid, int r, int c) {
	// base case
	if (!inArea(grid, r, c) return;
	
	// visit adjacent
	dfs(grid, r - 1, c);
	dfs(grid, r + 1, c);
	dfs(grid, r, c - 1);
	dfs(grid, r, c + 1);
}

bool inArea(vector<vector<int>>& grid, int r, int c) {
	return r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()；
}

网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。如何避免这样的重复遍历呢？答案是标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。

void dfs(vector<vector<int>>& grid, int r, int c) {
	// base case
	if (!inArea(grid, r, c) return;
	
	if (grid[r][c] != 1) return;
	grid[r][c] = 2;
	// visit adjacent
	dfs(grid, r - 1, c);
	dfs(grid, r + 1, c);
	dfs(grid, r, c - 1);
	dfs(grid, r, c + 1);
}

bool inArea(vector<vector<int>>& grid, int r, int c) {
	return r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size();
}

岛屿的最大面积

LeetCode-695 岛屿的最大面积

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        int r = grid.size(), c = grid[0].size();

        for (int row = 0; row < r; row++) {
            for (int col = 0; col < c; col++) {
                int area = dfs(grid, row, col);
                max_area = max(max_area, area);
            }
        }
        return max_area;
    }
private:
    int max_area = 0;
    bool inArea(vector<vector<int>>& grid, int r, int c) {
        return r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size();
    }

    int dfs(vector<vector<int>>& grid, int r, int c) {
        if (!inArea(grid, r, c) || grid[r][c] != 1) return 0;
        grid[r][c] = 2;
        return 1
        + dfs(grid, r-1, c)
        + dfs(grid, r+1, c)
        + dfs(grid, r, c-1)
        + dfs(grid, r, c+1);
    }
};

岛屿的周长

LeetCode-200 岛屿的周长
岛屿的周长是计算岛屿全部的「边缘」，而这些边缘就是我们在 DFS 遍历中，dfs 函数返回的位置。观察题目示例，我们可以将岛屿的周长中的边分为两类，如下图所示。黄色的边是与网格边界相邻的周长，而蓝色的边是与海洋格子相邻的周长。

当 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候，就经过了一条黄色的边；
当函数因为「当前格子是海洋格子」返回的时候，就经过了一条蓝色的边。这样就把岛屿的周长跟 DFS 遍历联系起来了。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        int r = grid.size(), c = grid[0].size();

        for (int row = 0; row < r; row++) {
            for (int col = 0; col < c; col++) {
                if (grid[row][col] == 1) {
                    return dfs(grid, row, col);
                }

            }
        }
        return 0;
    }
private:
    bool inArea(vector<vector<int>>& grid, int r, int c) {
        return r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size();
    }

    int dfs(vector<vector<int>>& grid, int r, int c) {
        // base case
        if (!inArea(grid, r, c)) return 1;
        
        if (grid[r][c] == 0) return 1;
        if (grid[r][c] != 1) return 0;

        grid[r][c] = 2;
        // visit adjacent
        return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
    }
};

秒客网