图论第1天----第797题、第200题、第695题

# 图论第1天----第797题、第200题、第695题

文章目录

一、第797题--所有可能的路径
二、第200题--岛屿数量
三、第659题--岛屿的最大面积

又继续开始修行，把图论这块补上，估计要个5-6天时间。

一、第797题–所有可能的路径

图的dfs3部曲，跟2叉树的dfs3部曲很像，分为：函数参数、终止条件、当前节点出发路径的处理（带有回溯）。下面两个是核心思路：

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

本题处理的是有向无环图，相对简单一些，我个人感觉遇到由环的图要麻烦很多，要记录路径，后面遇到的时候再看了。在外部定义一个dfs函数，再用allPathsSourceTarget去调用这个函数。

class Solution {
private:
    vector> result;
    vector path;
    void dfs(vector>& graph, int node){
        if(node == graph.size()-1){
            result.push_back(path);
            return;
        }
        for(auto i: graph[node]){
            path.push_back(i);
            dfs(graph, i);
            path.pop_back();
        }
    }

public:
    vector> allPathsSourceTarget(vector>& graph) {
        path.push_back(0);
        dfs(graph, 0);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二、第200题–岛屿数量

分2个函数。numIslands去找起点，从哪块算是一个岛屿的起点，并计数；dfs是根据起点遍历矩阵，找连通域，遍历连通域中每一个矩阵元素。

思路上还可以，就是实现上有些麻烦。这里的dfs函数不需要定义终止条件，因为调用的函数会明确，在什么情况下调用。

class Solution {
public:
    int dir[4][2] = {0,1,1,0,0,-1,-1,0};
    void dfs(vector>& grid, vector>& visited, int x, int y){
        for (int i=0; i<4; i++){
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];

            if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size()) continue;
            if(!visited[nextx][nexty] && grid[nextx][nexty] == '1'){
                visited[nextx][nexty] = true;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

    int numIslands(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int result = 0;
        vector> visited(n, vector(m, false));
        for(int i = 0; i

广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后在回溯。
广搜的搜索方式就适合于解决两个点之间的最短路径问题。

下面是广搜法（bfs）的程序，直接上答案，没有做题。通过队列去实现。bfs后面再慢慢体会吧。

class Solution {
private:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector>& grid, vector>& visited, int x, int y) {
    queue> que;
    que.push({x, y});
    visited[x][y] = true; // 只要加入队列，立刻标记
    while(!que.empty()) {
        pair cur = que.front(); que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                que.push({nextx, nexty});
                visited[nextx][nexty] = true; // 只要加入队列立刻标记
            }
        }
    }
}
public:
    int numIslands(vector>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector> visited = vector>(n, vector(m, false));

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    result++; // 遇到没访问过的陆地，+1
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
};
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

三、第659题–岛屿的最大面积

跟上一题差不多，就是把统计数量改成统计最大值，其他都一样。

class Solution {
public:
    int dir[4][2] = {0,1,1,0,0,-1,-1,0};
    int count;
    
    void dfs(vector>& grid, vector>& visited, int x, int y){
        for(int i = 0; i<4; i++){
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if(nextx<0 || nextx>=grid.size() || nexty<0 || nexty>=grid[0].size()) continue;
            if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
                count++;
                visited[nextx][nexty] = true;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

    int maxAreaOfIsland(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int result = 0;
        vector> visited(n, vector(m, false));
        for(int i=0; i