图问题——深度和广度遍历，剑指offer专项105-107

剑指 Offer II 105. 岛屿的最大面积

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

广度优先遍历

设置一个访问标记数组
设置一个移动数组 ，vector dirs{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
设置一个访问队列，元素是二维的，因此需要用二维标识每个元素 queue> que
一个大的循环让每个节点都进入遍历函数（如果已经被标记就不用进入），遍历函数里面将这个节点加入队列进入循环
1、弹出 2、执行逻辑 3、加入后续节点

大的遍历
移动

遍历主逻辑

class Solution {
private:
    // BFS
    int countArea(vector<vector<int>>& grid, vector<vector<int>>& dirs, vector<vector<bool>>& visited, int i, int j) {
        //用一个队列存放元素，由于是二维因此需要两个元素指定坐标
        queue<pair<int, int>> que;
        que.push({ i, j });  
        visited[i][j] = true;

        int area = 0; //存放面积
        while (!que.empty()) {
            auto pos = que.front(); //获取队列头元素后再弹出
            que.pop();
            area++;                 //对元素执行的操作
            //继往开来 加入后续的元素过程
            for (auto& d : dirs) { //对四个方向进行遍历 
                int r = pos.first + d[0];//第一个元素为行移动
                int c = pos.second + d[1];//第二个元素为列移动
                if (r >= 0 && r < grid.size() &&//如果移动后不超左边界，右边界，上边界，下边界
                    c >= 0 && c < grid[0].size() &&//并且没被访问过，而且有元素，那么将其加入队列
                    grid[r][c] == 1 && !visited[r][c]) {
                    que.push({ r, c });
                    visited[r][c] = true;
                }
            }
        }
        return area;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        //定义一个已访问数组，初始化全设为0
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int maxArea = 0; //记录最大岛屿面积
        //{1, 0}表示向右移动 {-1, 0}表示向左移动  {0, 1}表示向下移动  {0, -1}表示向上移动
        vector<vector<int>> dirs{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {   //如果是1并且没有被访问，那么进入递归
                     //传递这个网格，dirs，已访问名单，当前行，列
                    int area = countArea(grid, dirs, visited, i, j);
                    maxArea = max(area, maxArea); //更新最大岛屿面积
                }
            }
        }
        return maxArea;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

深度优先遍历

和广度优先差不多，只是把队列换成了栈，
队列先进先出，那么第一个节点出队列，把它的孩子都加上，下一个运行的并不是这些孩子
栈后进先出，那么第一个节点出栈，把它的孩子都加上，下一个运行的就是这些孩子

虽然访问的顺序不一样，但是代码几乎相同

仅仅是将队列换成了栈

剑指 Offer II 106. 二分图

剑指 Offer II 107. 矩阵中的距离

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        //dists 保存各个格子距离最近的0的位置
        vector<vector<int>> dists(mat.size(), vector<int>(mat[0].size()));
        //访问队列
        queue<pair<int, int>> que;
        //dirs为移动方向
        vector<vector<int>> dirs{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

        //遍历这个数组
        for (int i = 0; i < mat.size(); ++i) {
            for (int j = 0; j < mat[0].size(); ++j) {
                //初始化dists，如果数字本身为0，那么距离就是0 否则初始化为无穷大
                if (mat[i][j] == 0) {
                    dists[i][j] = 0;       //dists保存到0的位置，本身为0则设置为0
                    que.push({ i, j });  //将所有本身为0的节点加入到队列中
                }
                else {
                    dists[i][j] = INT_MAX; //dists本身不为0设置为无穷大
                }
            }
        }

        while (!que.empty()) {
            auto pos = que.front();
            que.pop();
            //dist为距离最近0的位置
            int dist = dists[pos.first][pos.second];
            for (auto& d : dirs) {  //对上下左右进行遍历
                int r = pos.first + d[0];
                int c = pos.second + d[1];
                //保证不出界
                if (r >= 0 && r < mat.size() && c >= 0 && c < mat[0].size()) {
                    //对这个元素 上下左右进行判断，只将
                    if (dist + 1 < dists[r][c]) {
                        dists[r][c] = dist + 1;
                        que.push({ r, c });
                    }
                }
            }
        }
        return dists;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

图遍历总结

1、广度优先遍历类似层序遍历，它是有层次关系的，在以后涉及图的层序遍历就用广度优先，类似树，但比树更高级的是它可以决定树的根节点可以有多个节点。
深度优先遍历就是针对树进行前中后序遍历

2、一般图是用二维数组来表示，针对图上的点上下左右的移动可以通过

vector<vector<int>> dirs{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

for (auto& d : dirs) {  //对上下左右进行遍历
                int r = pos.first + d[0];
                int c = pos.second + d[1];
              判断出界
             if (r >= 0 && r < mat.size() && c >= 0 && c < mat[0].size()) {
                    dists[r][c]就是上下左右的元素
                }          
 }
1
2
3
4
5
6
7
8
9
10

3、还有个标记访问数组，在传递给函数时要用&来接收

vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
1

4、这两个遍历的代码一个样，只是区别在于用得队列还是栈