11.图论_图的复杂度

1.整体看搜索

1.1 搜索中几个重要的概念

** 对于数据结构来说：** 搜索分为图的搜索，矩阵的搜索，树的搜索，其中树的搜索可以转化为图的搜索

时间复杂度：O(MN) 就是二维数组的大小

**从搜索的角度又分为两种：**深搜 DFS 和广搜 BFS

在遍历的时候有三种数组：

邻接矩阵 A —> 代表节点和节点之间的连接关系，只有有了邻接矩阵才能知道下一步要往哪里走，对于图来说要搞清楚是有向图还是无向图

visited 数组 —> 判断是否以 cur 为起点进行了 dfs 或者 bfs 就要用 visited 数组记录，因为有时候我们可能会在遍历 A 时 从 node A-> node B ，然后遍历 B 时又从 node B->node A ，那么 A 就被遍历了两次，造成 A->B 死循环。但如果是”不会走回头路“的遍历就不需要 visited ,比如后面的 N皇后题，它不会再往上走了，与此同时如果我们也会原地记录，比如 nums[i] [j] 本来是 . 遍历完之后会将其置为 X ，那这样就不需要额外的 visited 用来记录了

入度 in —> 代表每个节点的入度，一般用于判断是否有环

1.2 dfs 函数模板

深度优先搜索是先从一个节点 cur 开始，然后遍历 cur ，再然后遍历 cur 所有可以到达的子节点，再再然后遍历 cur 的子节点。。。。

1.参数与返回值

参数的话需要传入我们当前需要遍历哪个节点；A 也就是遍历的路径；visited 判断该点是否已经遍历

2.返回值

关于什么时候有返回值，什么时候没有返回值

有返回值：

①在某个中间节点就可以找到答案

在中间过程出现了答案（不论这个答案是对还是错），再往下多走一步都是多余则可以向上返回了

这个题可以参考，因为关于这个节点再往下多走一步就会出错，所以当到达临界值是就不再向下判断

②这个返回值可以是 int 可以是 bool

③从头遍历到尾且答案唯一

这种情况可以借鉴 N 皇后和解数独，数独是主要找到那个点我们就返回，因为他答案唯一，再往下多找一步都多余

没有返回值：

①从头遍历到尾，当 for 循环结束时这个 dfs 也就自己结束了

②从头遍历到尾且存在多个答案

比如 N 皇后问题，他就要从头遍历到尾，但是答案有多种，如果我们对某个树叶进行 return ,后面的树叶就不会再遍历了

XXXX dfs(int i,int j,vector<vector<int>>& A,vector<vector<bool>>& visited){
  if(判断是否到达边界) return;
  // 开始往深处遍历
  for(auto [dr,dc]:vector<vector<int>>{{1,0},{-1,0},{0,-1},{0,1}}){
    int nr = i+dr;
    int nc = j+dc;
    if(判断 A[i][j] 是否满足往深里遍历的条件){
      visited[i][j] = true;
      if(dfs(nr,nc,A,visited)) return true; // 是否要从这一步进行截断
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3 起始节点的问题

上面说了 dfs 函数，是从 cur 这个节点出发深度遍历，但是有时候节点可能从多个方向出发，所以在核心方法中要用一个 for 循环，然后从 for 循环中依次调用 dfs 方法

矩阵的：

for(int i = 0;i<row;i++){
  for(int j = 0;j<col;j++){
    dfs(i,j,A,visited);
  }
}
1
2
3
4
5

树的：

res+=dfs(root,targetSum); // 先得到树根的
if(root->left) res+=pathSum(root->left,targetSum); // 以左右节点出发
if(root->right) res+=pathSum(root->right,targetSum);
1
2
3

2. 图的搜索

对于图搜来说第一步要创建邻接矩阵，邻接矩阵代表节点与节点之间的连接情况

邻接矩阵有两种，一个是 N*N 的，一个是 N * M 的

N*N 表示 vector 中每个节点的关系都会得到映射，不是 1， 就是 0

N*M表示 vector 只映射与该 node 相连的节点，那么存放的就是该 node 的 val 值

图的应用有多种：连通图的个数，图中是否存在闭环

需要关注的点：

判断是以随便一个起点开始遍历还是以确定的 start 开始遍历

2.1 BFS

深度遍历的核心思想以 cur 为出发点，遍历所有与 cur 相连的节点 next ，然后再以next 为出发点，遍历 next 的 next

关于 bfs size 的问题：

像树的 bfs 在遍历的时候是有 size 的，但是像岛屿的数量在遍历的时候是没有 size 的。有 size: 一次遍历从 cur 到其相同步数的 node ，没有 size 一次会遍历一片 node ，不论 cur 到 node 会走多少步

2.2 DFS

广度优是搜索一层一层地进行遍历，以 cur 作为起点遍历，将 cur 的 nexts 全部放入 queue 中，遍历一个距离能访问到的所有节点

2.3 拓扑排序

拓扑排序一般是一个有向无环图，是 BFS 的特殊情况

S1：遍历图，计算每个节点的入度，将该图的邻接矩阵表示出来

S2：将入度为 0 的节点加入 queue 中

S3：从 que 中弹出一个节点，将和这个节点连接的节点的入度都置为 1

​ 如果子节点的入度为 0 ，则将此节点添加到 que 中

S4：如果 que 中节点个数为 null 但是还存在入度为 1 的节点则说明存在环

2.3_127. 单词接龙

我们以 hit 为出发点进行广度优先搜索，一旦搜到了终点，那么路径就是最短的

S1：先将 hit 放入 queue 中，对其每一个字符进行枚举

S2：先枚举 h 位，枚举 a~z 判断是否在 word_list 中，再枚举 i 位判断是否在 a~z 中，其中 hot 在 list 中，将 hot 放入 queue ，并且为了防止后面枚举过程中又会枚举到 hot 所以将 hot 设置为 visited 的状态，最后枚举 t 位

S3：从 hot 出发继续向下枚举，从 hot 的 h 开始枚举，枚举 a~z，然后将 dot 放入

通过上面的不断枚举，不断的将 node 放到 que 最后其实会组成一个无向图，相当于求从 hit 到 cog 的最短路径

2.3.2 算法描述

class Solution {
  public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    queue<string> que;
    que.push(beginWord);
    unordered_set<string> word_set(wordList.begin(),wordList.end());
    word_set.erase(beginWord);
    if(!word_set.count(endWord)) return 0;
    unordered_set<string> visited;
    visited.insert(beginWord);    
    int step = 0;
    int n = beginWord.size();
    while(!que.empty()){
      step++; // 多了一层
      int size = que.size();
      for(int i = 0;i<size;i++){
        string cur = que.front();
        que.pop();
        for(int k = 0;k<n;k++){
          char c = cur[k];
          for(char w = 'a';w<='z';w++){
            cur[k] = w;
            if(word_set.count(cur)){
              if(cur==endWord) return step+1;
              if(!visited.count(cur)){
                que.push(cur);
                visited.insert(cur);
              }
            }
            visited.insert(cur);
          }
          cur[k] = c;
        }
      }
    }
    return 0;
  }
};
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

2.5_752. 打开转盘锁

2.5.1 算法描述

这个题和 127 的区别在于我们下一跳可以去的地方是不同的，127下一跳可以去到 a~z ，但是本体是一个转盘，下一次只能去到下一位数，其他的地方是没有区别的

2.5.2 算法描述

class Solution {
  public:
  int openLock(vector<string>& deadends, string target) {
    queue<string> que;
    que.push("0000");
    unordered_set<string> visited(deadends.begin(),deadends.end());
    if(visited.count("0000")) return -1;
    if("0000"==target) return 0;
    visited.insert("0000");
    int step = 0;
    while(!que.empty()){
      step++;
      int size = que.size();
      for(int i = 0;i<size;i++){
        string cur = que.front();
        que.pop();
        for(int j = 0;j<4;j++){
          for(int t = -1; t < 2; t += 2){
            char a = (cur[j] -'0' + 10 + t) % 10 + '0';
            string new_cur = cur;
            new_cur[j] = a;
            if(target==new_cur) return step;
            if(!visited.count(new_cur)){
              que.push(new_cur);
              visited.insert(new_cur);
            }
          }
        }
      }
    }
    return -1;
  }
};
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

2.3.1 算法描述

无向图中两个顶点之间的最短路径的长度，可以通过广度优先遍历得到

2.4 判断连通图的个数

判断连通图的个数也就是判断有几个图 LeetCode 547

1.DFS 方法

从某一个节点为起始点出发，遍历其连接的节点，再通过递归的方式遍历相连节点的相连节点。当一但退出了递归，代表这个 node 所有相连的节点和间接相连的节点和间接的间接相邻的节点都遍历完成，也就是一个连通图

class Solution {
  public:
  int count = 0;
  void dfs(vector<vector<int>>& isConnected, vector<bool>& visited,int i){
    int n = isConnected.size();
    if(visited[i]) return;
    visited[i] = true;
    for(int j = 0;j<n;j++){
      if(isConnected[i][j]){
        dfs(isConnected,visited,j);
      }
    }
  }
  int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    // 判断某个点是否 dfs 过
    vector<bool> visited(n,false);
    for(int i = 0;i<n;i++){
      if(visited[i]==false){
        dfs(isConnected,visited,i);
        count++;

      }
    }
    return count;

  }
};
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

2.BFS 方法

这里也是先从某一个节点开始，然后遍历邻接矩阵将和其所有相连的节点加入 queue ，一旦 queue 中没有 node 时代表一个连通图结束，为了防止重复遍历节点这里还需要一个 visited 数组

class Solution {
  public:
  int findCircleNum(vector<vector<int>>& isConnected) {
    // bfs 判断是否是连通图
    int n = isConnected.size();
    vector<bool> visited(n,false);
    int cnt = 0;
    // 开始遍历节点
    for(int i = 0;i<n;i++){
      if(!visited[i]){
        cnt++;
        queue<int> que;
        que.push(i);
        while(!que.empty()){
          int cur = que.front();
          que.pop();
          visited[cur]=true;
          for(int j = 0;j<isConnected[cur].size();j++){
            if(isConnected[cur][j]&&!visited[j]) que.push(j);
          }
        }
      }   
    }
    return cnt;
  }
};
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

2.5 图中是否存在闭环

详见：LeetcCode 207

2.1_207课程表

2.1.1 算法描述

1.题意

首先这个题因为有相互的指向，所以是一个有向图

其次因为课程之间相互依靠，但是总有一个起始课程，所以这是一个无环图。一个有向图并且无环最终得到一个拓扑图。本题的主要目的是判断该图是否存在环

对于深度优先判断环：为每个节点增加判断的状态，如果一个节点重复是“已判断”状态代表出现了环

对于广度优先搜索判断环：对加入到栈中的元素进行判断，并记录判断元素的个数，如果一个元素判断过多次则最后判断个数 > 节点个数，说明存在环

其实这里还有一个映射关系，就是 v 的值和 index 是映射的

2.如何深度优先搜索

S1：遍历题目给的图 prerequisites，生成 edges

S2：随便找一个点为起始点进行深度优先遍历。下一次深度优先遍历时将他的子孩子作为起始点不断一层层的向下遍历

这里可以用深度搜索遍历的原因是，深度优先搜索使用的数据结构是栈。我们先将出度为 0 的节点放入，而出度为 0 的节点是比较高级的课程，基础的课程后入栈那么也就先出

S1：记录节点之间的映射关系

key：父节点；value：该父节点指向的相邻节点

比如：在课程中基础课程指向高级课程。有一个数据结构存储节点之间的关系，key ：课程 ； value ：该课程对应的高级课程

其中图中的「白色」「黄色」「绿色」节点分别表示「未搜索」「搜索中」「已完成」的状态

S2：逐个遍历节点

在遍历节点时不要按照什么规则，直接从 index 为 0 的节点开始遍历即可。从 A 开始遍历，一直遍历到 G 没有出度节点为止，就到达了最底层

S2：入栈+回溯

遍历到 G 了，G 是没有出度节点的，所以将 G 入栈，因为这是一个递归过程，G 是最深层的节点后再去回溯 F ，然后同理将 E 入栈。然后 F 入栈

S3：最后再返回到 A 节点

2.广度优先所搜

S1：计算每个节点的入度和出度

入度为 0 的节点说明是基础节点，基础节点应该先被遍历然后先被输出，所以这里使用队列作为数据结构

S2：首先遍历入度为 0 的节点

B 节点的入度是 0 所以先将 B 放入队列中

S3：一个节点遍历完成后，更改其相邻节点的入度

S4：继续遍历队列，直到队列为空

继续遍历队列，每处理队列中的一个节点首先要将其进行输出，然后将其相邻接点的入度 -1

2.1.2 代码实现

1.深度优先

class Solution {
  public:
  bool valid = true;
  void dfs(int u,vector<vector<int>>& edges,vector<int>& state){
    state[u]= 1;
    // 开始深度遍历
    for(int i = 0;i<edges[u].size();i++){
      if(edges[u][i]==1){ // 连通
        if(state[i]==0){
          dfs(i,edges,state);
        }else if(state[i]==1){
          valid=false;
          return;
        }
      } 
    }
    state[u] = 2;
  }
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> edges(numCourses,vector<int>(numCourses,0)); // 定义二维数组
    vector<int> state(numCourses,0); // 记录每个节点的搜索状态;0:未搜索1搜索中,2搜索完成
    // 形成映射关系
    for(int i = 0;i<prerequisites.size();i++){
      int a = prerequisites[i][0];
      int b = prerequisites[i][1];
      edges[b][a] = 1;
    }
    // 开始遍历
    for(int i = 0;i<numCourses;i++){
      if(state[i]==0){
        dfs(i,edges,state);
      }
    }
    return valid;

  }
};
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

2.广度优先

class Solution {
  public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    // 定义两个 vector 
    vector<vector<int>> edges(numCourses,vector<int>(numCourses,0));
    vector<int> in(numCourses,0);
    // 初始化
    for(int i = 0;i<prerequisites.size();i++){
      int a = prerequisites[i][0];
      int b = prerequisites[i][1];
      edges[b][a] = 1;
      in[a]++;
    }
    // 先将所有入度为 0 的点进行加入
    queue<int> que;
    for(int i = 0;i<in.size();i++){
      if(in[i]==0) que.push(i);
    }
    // 开始遍历
    int visited = 0;
    while(!que.empty()){
      visited++;
      // 先弹出一个 node ,然后将其四周的点的入度进行 -1
      int u = que.front();
      que.pop();
      // 判断和其相连的点
      for(int i = 0;i<edges[u].size();i++){
        if(edges[u][i]==1){ // 易错点。不能是因为一开始 in 是 0 ,而是因为被减掉造成的 in 是 0 才将其加入 que ，否则会出现 que 又重复的现象
          in[i]--; 
          if(i!=u&&in[i]==0) que.push(i);
        } 
      }
    }
    if(visited==numCourses) return true;
    else return false;

  }
};
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

2.1.3 时空复杂度

时间复杂度：

图的深度和广度搜素的时间复杂度都是 O（v+e）,也就是节点个数+变得个数

空间复杂度：

深度和广度都是 O(v+e) 因为他们要存储成邻接表的映射关系，与此同时还需要栈或者队列进行辅助，他们的空间复杂度是 O(v) ,所以最后的空间复杂度是 O(v+e)

4. 矩阵的搜索

4.1 DFS

DFS 一般是从一个点出发然后遍历到其他所有点，DFS 一般包含两个函数，一个是 DFS 的入口函数一个是 DFS 函数

入口函数：定义 for 循环，把所有可能的起始位置进行遍历

DFS 函数：这是一个递归函数，想一下函数参数，返回值；终止条件；循环的函数体

函数参数：①数据数组②记忆递归数组 dp ③当前遍历的起始位置

返回值： 如果有了 dp 一般是不需要返回值的，我们直接将结果保存在 dp 中

终止条件：dp 中对应的位置有值

循环的函数体：一般是从该点出发去往 cur 所有可以到达的地方

回溯和 DFS 的区别：

DFS 是一直向下走，如果不满足要求则返回到上一层

回溯是在 DFS 的基础上，当不满足条件会再去下一个分支

4.2 BFS

这里同样用一个 queue 实现，在没有告知初始起点是谁的情况下使用双重 for 循环对每一个点进行遍历

将同一片的岛屿放到同一个 queue 中

4.2.1 岛屿的数量

详见 LeetCode 200

1.DFS

class Solution {
  public:
  int nums_lands = 0;
  void dfs(vector<vector<char>>& grid,int i,int j){
    // cout<<"i:"<<i<<"j:"<<j<<endl;
    int nr = grid.size();
    int nc = grid[0].size();
    // 将其上下左右四个点设为 0
    grid[i][j] = '0';
    if(i>0&&grid[i-1][j]=='1') dfs(grid,i-1,j);
    if(i<nr&&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<nc&&grid[i][j+1]=='1') dfs(grid,i,j+1);
  }
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    int nc = grid[0].size();
    // DFS
    for(int i = 0;i<nr;i++){
      for(int j = 0;j<nc;j++){
        if(grid[i][j]=='1'){
          nums_lands++;
          dfs(grid,i,j);
        }
      }
    }
    return nums_lands;
  }
};
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

2.BFS

class Solution {
  public:
  /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
  int num_count = 0;
  int solve(vector<vector<char> >& grid) {
    // write code here
    // bfs
    for(int i = 0;i<grid.size();i++){
      for(int j = 0;j<grid[i].size();j++){
        int Row = grid.size();
        int Col = grid[i].size();
        if(grid[i][j]=='1'){
          queue<pair<int,int>> que;
          que.push({i,j});
          num_count++;
          while(!que.empty()){
            int cur_i = que.front().first;
            int cur_j = que.front().second;
            que.pop();
            for(auto [dr,dc]:vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
              if(cur_i+dr<Row&&cur_i+dr>=0&&cur_j+dc<Col&&cur_j+dc>=0&&grid[cur_i+dr][cur_j+dc]=='1'){
                grid[cur_i+dr][cur_j+dc] = '0';
                que.push({cur_i+dr,cur_j+dc});
              }
            }
          }
        }
      }
    }
    return num_count;
  }
};
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

2.2.3 空间复杂度

BFS：O(MN)，整个二维数组全是陆地

DFS：O(min(M,N)) , 最坏情况全部为陆地

2.3_490迷宫

1.算法描述

这个题和之前题型不同之处在于，本题从某个点出发进行广搜，并且在进行广搜时我们还要跳着广搜。所以这和普通的广搜不同之处在于

（1）开始广搜的出发点不同

（2）不是每搜到一个点就要放入 que 中，只有满足条件才放入 que 中

（3）没有办法动态改变 maze 的值：需要记忆矩阵

这里每一次 BFS 时不是一次走一步，而是一直走走到尽头，所以在四个方向的 for 循环中还有一个 while 循环来控制每次走到尽头

易错点：

在一开始将 que pop 的时候就要判断 cur 是否是终点，而不是等到 cur 移动到第一个位置上时才判断

2.代码实现

class Solution {
  public:
  bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    int Row = maze.size();
    int Col = maze[0].size();
    // 广度搜索
    queue<pair<int,int>> que;
    que.push({start[0],start[1]});
    vector<vector<bool>> visited(Row,vector<bool>(Col,false));
    while(!que.empty()){
      // 遍历这个 node 周围的点
      int r = que.front().first;
      int c = que.front().second;
      visited[r][c] = true;
      que.pop();
      // 判断该点是否是终点
      if(r == destination[0]&&c == destination[1]) return true;
      for(auto[dr,dc]:vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
        int nr = r+dr;
        int nc = c+dc;
        // 再以该点为出发点遍历其他的点
        while(nr>=0&&nr<Row&&nc>=0&&nc<Col&&maze[nr][nc]==0){
          nr+=dr;
          nc+=dc;
        }
        // 跳出循环了说明该点不通过
        nr-=dr;
        nc-=dc;
        // 最终落入点添加到 que
        if(visited[nr][nc]==false) que.push({nr,nc});
      }

    }
    return false;
  }
};
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

2.4.3.时空复杂度

时间复杂度：O(MN) MN 分别是迷宫的宽高

要计算 cur 节点到二维数组每个节点的广搜，所以是 O(MN)

空间复杂度：O(MN)

2.4_505 迷宫2

参考链接

2.4.1.算法描述

这个题记录的是从点 cur 到其他点的最短路径。最短路径可以使用广搜也可以使用地杰斯特拉算法

本题特点：

①需要创建一个 dist 用于记录 cur 到其他 node 的最短路径

②不需要记忆数组，因为本题特点每个点只会被放入到 que 中一次

2.4.2 代码实现

class Solution {
  public:
  int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    int Row = maze.size();
    int Col = maze[0].size();
    queue<pair<int,int>> que;
    que.push(pair<int,int>{start[0],start[1]});
    vector<vector<long long>> dist(Row,vector<long long>(Col,INT_MAX)); // 该 node 到其他所有 node 的距离值
    dist[start[0]][start[1]] = 0;
    while(!que.empty()){
      int r = que.front().first;
      int c = que.front().second;
      que.pop();
      for(auto[dr,dc]:vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
        int nr = r+dr;
        int nc = c+dc;
        int step = 1; // r,c 到 nr,nc 走了多少步
        while(0<=nr&&nr<Row&&0<=nc&&nc<Col&&maze[nr][nc]==0){
          nr+=dr;
          nc+=dc;
          step++;
        }
        nr-=dr;
        nc-=dc;
        step--;
        if(dist[r][c]+step<dist[nr][nc]){ // 找到了最短路径
          dist[nr][nc] = dist[r][c]+step;
          que.push(pair<int,int>(nr,nc)); // 这个点等待开锁
        }
      }

    }
    // 得到最大距离
    if(dist[destination[0]][destination[1]]==INT_MAX) return -1;
    else return dist[destination[0]][destination[1]];
  }
};
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

2.4.3 时空复杂度

时间复杂度：O(MN)

空间复杂度：O(MN)

2.8_417. 太平洋大西洋水流问题

2.8.1 算法描述

这个题使用 DFS 的方式，这里使用要使用两个 容器分别记录是否可以有 p 的水，是否可以有 a 的水

1.从哪个点出发

这样的话我们从特定的点出发，就是从两侧的点先出发向内走

2.DFS 方法

这里的 dp 可以反应节点的遍历情况

2.8.2 代码实现

class Solution {
  public:
  void dfs(vector<vector<bool>>& dp,vector<vector<int>>& heights,int i ,int j){
    int Row = heights.size();
    int Col = heights[0].size();
    dp[i][j] = true;
    // DFS
    for(auto [dr,dc]:vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
      int nr = i+dr;
      int nc = j+dc;
      if(nr<Row&&nr>=0&&nc<Col&&nc>=0&&heights[i][j]<=heights[nr][nc]&&!dp[nr][nc]){
        dfs(dp,heights,nr,nc);
      }
    }
  }
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size();
    int n = heights[0].size();
    if(m==0||n==0) return {};
    // 定义两个 dp 
    vector<vector<bool>> dp_p(m,vector<bool>(n));
    vector<vector<bool>> dp_a(m,vector<bool>(n));
    // 起始点位置,以
    // p 的遍历
    for(int i = 0;i<m;i++){
      // 从最左侧右侧出发遍历 pacific 
      dfs(dp_p,heights,i,0);
      dfs(dp_a,heights,i,n-1);
    }
    // a 的遍历
    for(int i = 0;i<n;i++){
      // 从上侧出发开始遍历
      dfs(dp_p,heights,0,i);
      dfs(dp_a,heights,m-1,i);
    }
    // 计算相交部分
    vector<vector<int>> res;
    for(int i = 0;i<m;i++){
      for(int j = 0;j<n;j++){
        if(dp_a[i][j]&&dp_p[i][j]){
          res.push_back({i,j});
        }
      }
    }
    return res;
  }
};
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

2.8.3 时空复杂度

时间复杂度：O(M*N)

因为矩形的每个点都要进行遍历，而且不会有重复遍历

空间复杂度：O(M*N)

2.9_130. 被围绕的区域

2.9.1 算法描述

解决这个题思路的关键点就是，如果这个 O 是在边缘上，则它能到达的所有 O 以及这些 O 能到达的 O 都不能被设为 X

其他的 O 都可以被设置为 X

所以解决本题的思路就是先遍历周围的点，然后在从周围的点继续 dfs ，将这些 DFS 到的点都用 ‘A’ 表示，剩下的 O 就是没有被连通到的 O

那么对于上面的可以连通到的 A 则再替换为 O ，连通的不到的 O 替换为 X 即可

2.9.2 代码实现

class Solution {
  public:
  void dfs(int i,int j,vector<vector<char>>& board){
    int Row = board.size();
    int Col = board[0].size();
    if(board[i][j]!='O') return;
    board[i][j]='A';
    for(auto [dr,dc] : vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
      int nr = i+dr;
      int nc = j+dc;
      if(nr<Row&&nr>=0&&nc<Col&&nc>=0) dfs(nr,nc,board);
    }
  }
  void solve(vector<vector<char>>& board) {
    // 先将边缘上相关的字母都搞成 A
    int m = board.size();
    int n = board[0].size();
    for(int i = 0;i<m;i++){
      dfs(i,0,board);
      dfs(i,n-1,board);
    }
    for(int i = 0;i<n;i++){
      dfs(0,i,board);
      dfs(m-1,i,board);
    }
    // 将 A 搞成 O，将 O 搞成 X
    for(int i = 0;i<m;i++){
      for(int j = 0;j<n;j++){
        if(board[i][j]=='A') board[i][j]='O';
        else if(board[i][j]=='O')  board[i][j]='X';
      }
    }

  }
};
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

4.3 含有限步数的搜索问题

**题目特点：**给定一个路径+起点+终点+可以走的步数，求一种有几种方法可以到达终点

因为是路径问题，我们同样可以用搜索的方式去做，就是从 row, col 出发，判断当剩余步数为 rest 的时候可以到达哪些地方

S1：记忆化数组 dp[row] [col] [rest] 代表什么

代表：我们从 [row ，col] 为起始点，当步数还剩下 rest 时，想要到达终点几种走法

不论怎么样，看到 dp[row] [col] 就知道他是以 row,col 为起点的就好了

S2：写 dfs 的函数

（1）参数和返回值

这个 dfs 是否需要返回值呢，在每一次 dfs 时都会以 row col 为起点判断我们还剩 rest 步的时候都可以去哪些地方，那么他们的递归子问题就是 【nr,nc】 这些点去到 end 有几种方法，我们需要将从 [row,col] 为起点，剩余步数为 rest 的所有可能进行累加，所以要有返回值

而且我们看到这个求得是方法数，所以就要将 row col 所有可以到达的路径进行累加，那更应该要有返回值

（2）跳出循环的判断

①如果 [row,col] 到达了终点 return 1

②dp[row] [col] [rest] 判断过了 return dp[row] [col] [rest] 则 return dp

③ rest<=0 return 0

(3) 以 row col 为起点，对于不同方向的判断

这就是看看 [row,col ] 可以去到哪些地方，然后使用 for 循环开始遍历了

3.树的搜索

什么时候用到

关于树的路径问题

如何使用：

这里对树的搜索是先将树转换为图的形式

S1：创建临界矩阵 A

将树转换为图这样方式的搜索中，我们一般都是将树转换为无向图，因为在有向图的时候 cur 节点只链接其左右子树，所以我们每一层遍历只需要向下走即可，但是在无向图中，cur 节点是还需要向上走的，所以可以通过判断这个树是否要向上走而选择是否构建邻接矩阵

void dfs(TreeNode* cur,vector<vector<int>>& A){
  if(!cur) return;
  if(cur->left){
    A[cur->val].push_back(cur->left->val);
    A[cur->left->val].push_back(cur->val);
    dfs(cur->left,A);
  }
  if(cur->right){
    A[cur->val].push_back(cur->right->val);
    A[cur->right->val].push_back(cur->val);
    dfs(cur->right,A);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

S2：对树进行 DFS or BFS

这里与图的使用一样，要加一个 visited 数组判断该点是否有被遍历过

有向图树的遍历和无向图树的遍历非常相似，只不过无向图树在遍历时方向是多向的，所以使用一个 for 循环去遍历和 cur 相连的节点

有向图在遍历的时候只能往左右两个方向走，所以 dfs 中只有一个 for 循环控制方向

其余的地方和普通树的遍历都是一样的

3.1 BFS

BFS 使用一个 queue ，因为这里存在一种 ” 层数 “ 的关系，所以每一次要在 while(!que.empty()) 里面再嵌套一层 for 循环去遍历 cur 下一层的所有节点，当遍历到第二次 for 的时候就是和 cur 相隔两层的 node

while(!que.empty()){
  int size = que.size();
  for(int i = 0;i<size;i++){ // 这一层 for 遍历的节点都是和 cur 相差相同层的
    int cur = que.front();
    que.pop();
    for(int next:A[cur]){
      if(!visited[next]) que.push(next);
    } 
  }
}
1
2
3
4
5
6
7
8
9
10

3.2 DFS

DFS 本身就是从 cur 出发一直往深里遍历，这里求得是距离

void dfs(int k,int root,int fa,int deep,vector<vector<int>>& A,vector<bool>& visited){
  visited[root] = true;
  if(deep==k){ // 某个让 dfs 循环停止的条件
    res.push_back(root);
  }else if(deep>k) return;
  for(int next:A[root]){
    if(!visited[next]) dfs(k,next,root,deep+1,A,visited);
  }
}
1
2
3
4
5
6
7
8
9

3.3 起始节点不固定

2.11_863. 二叉树中所有距离为 K 的结点

2.11.1 算法描述

1.bfs

因为是距离为 k ，所以这个方向也可能是向上走的，然后我们在以 target 为起点就像剥洋葱一样一层层的拨开，这里使用的是广度遍历

当剥到第 k 层的时候就不用再拨了

因为是 bfs 所以最后 queue 中还剩余的节点就是和 target 相差 k 层的节点

所以先生成树的邻接矩阵，然后我们再对 node 进行 bfs 就好了

2.12.2 代码实现

1.bfs

class Solution {
  public:
  void dfs(TreeNode* cur,vector<vector<int>>& A){
    if(!cur) return;
    if(cur->left){
      A[cur->val].push_back(cur->left->val);
      A[cur->left->val].push_back(cur->val);
      dfs(cur->left,A);
    }
    if(cur->right){
      A[cur->val].push_back(cur->right->val);
      A[cur->right->val].push_back(cur->val);
      dfs(cur->right,A);
    }
  }
  vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    vector<vector<int>> A(501);
    vector<bool> visited(501);
    vector<int> res;
    if(!root) return res;
    // 生成邻接矩阵
    dfs(root,A);
    // 层次遍历邻接矩阵
    queue<int> que;
    que.push(target->val);
    visited[target->val] = true;
    int depth = 0;
    while(!que.empty()){
      if(depth==k) break;
      int size = que.size();
      for(int i = 0;i<size;i++){
        int cur = que.front();
        que.pop();
        for(int next:A[cur]){
          if(visited[next]) continue;
          que.push(next);
          visited[next] = true;
        }
      }
      depth++;
    }
    while(!que.empty()){
      res.push_back(que.front());
      que.pop();
    }
    return res;
  }
};
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

2.dfs

class Solution {
  public:
  void  create(TreeNode* root,vector<vector<int>>&A){
    if(!root) return ;
    if(root->left){
      A[root->val][root->left->val] = 1;
      A[root->left->val][root->val] = 1;
      create(root->left,A);
    }
    if(root->right){
      A[root->val][root->right->val] = 1;
      A[root->right->val][root->val] = 1;
      create(root->right,A);
    }
  }
  void dfs(int cur,int k,vector<int>& res,vector<vector<int>>& A,vector<bool>& visited){
    if(visited[cur]) return;
    if(k==0){
      res.push_back(cur);
      return;
    } 
    visited[cur] = true;
    for(int i = 0;i<501;i++){
      if(A[cur][i]==1&&visited[i]==false){
        dfs(i,k-1,res,A,visited);
      }
    }
  }
  vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    vector<vector<int>> A(501,vector<int>(501,0));
    create(root,A);
    //bfs
    vector<bool> visited(501,false);
    vector<int> res;
    dfs(target->val,k,res,A,visited);
    return res;

  }
};
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

2.5_329. 矩阵中的最长递增路径

参考资料

2.5.1 算法描述

这里使用 DFS+记忆递归的方法

如果是使用 dfs 的思路，假设说我们现在以 4 为起始点，进行 DFS 时会将其上下左右四个点进行遍历。但是在遍历 (0,1) 那个 9 的时候发现 9 是之前遍历过的，所以这里就不再以 9 为起始点进行遍历了

memo 是一个 dp 的方式，存储了该节点为出发点时能到达的最长路径，这个矩阵不仅记录该点可以到达的最大路径。同样也类似于一个 visited 数组，如果该点判断过了那么久不用再判断了，谁调用的该点，则直接加上该点的数据即可

假设说现在要遍历 4

S1：以 上下左右的方式进行遍历。4 只能向下走，这时候先不对 4 进行赋值

S2：4 先走到了 8 ，走到 8 发现，8 不能再走了，所以这时候 8 的 memo 的值为 1

S3：这时候返回到 4 ，4 会得到 8 的返回值，然后比较 8 的值和 4 其他方向值，谁大，谁大谁就方法在 4 上

DFS 需要注意的点

什么时候 DFS 会终止 DFS 。如上图所示，在遍历 (0,0) 这个 9 的时候，其上下左右没有可以继续 DFS 的 node 了，因为他的上下左右都不符合递增的条件。所以这个时候 DFS 就会停止，返回到双重 for 循环中，接着遍历下一个节点

易错点：

这里在 main 函数中要从矩阵的每个点都为起点开始遍历

2.5.2 代码实现

class Solution {
  public:
  int dfs(int r, int c,vector<vector<int>> &matrix,vector<vector<int>> &memo) {
    int Row = matrix.size();
    int Col = matrix[0].size();
    if (memo[r][c] != 0) {
      return memo[r][c];
    }
    ++memo[r][c];
    for (auto [dr,dc]:vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}){
      int nr = r+dr;
      int nc = c+dc;
      if(nr>=0&&nc>=0&&nr<Row&&nc<Col&&matrix[r][c]<matrix[nr][nc]) {
        memo[r][c] = max(memo[r][c], dfs(nr, nc,matrix, memo) + 1);
      }
    }
    return memo[r][c];
  }
  int longestIncreasingPath(vector< vector<int>> &matrix) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
      return 0;
    }
    int Row = matrix.size();
    int Col = matrix[0].size();
    vector<vector<int>> memo(Row,vector<int>(Col,0));
    int res = 0;
    for (int i = 0; i < Row; ++i) {
      for (int j = 0; j < Col; ++j) {
        res = max(res, dfs(i,j,matrix,memo));
      }
    }
    return res;
  }
};
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

2.5.3 时空复杂度

时间复杂度：O()

空间复杂度：O(mn)

2.6_

2.7_310. 最小高度树

参考资料

2.7.1 算法描述

这个题要求的是最小高度树的树根，那么这个最小高度树的树根的特点就是以它为节点，向下数时他的层数要少

这里不能单纯的使用入度的多少就判断这个节点的层数，如下图：

node 4 的入度就比较少，但是他的高度和 node 3 是相同的

那么这个题就转换成了不断的寻找，直到找到入度最大那个节点

步骤类似于剥洋葱，不断地将入入度为 0 的节点剥掉剩下的就是入度多的节点，如下图所示，入度多的节点如果作为根节点的话就是最小高度树

暴力法：层次遍历

这里使用层次遍历的方法，以树的每个节点都作为 root 节点，然后使用层次遍历计算每个 node 的高度

这样最后是超时的

从下向上的层次遍历：拓扑排序

拓扑排序：应用场景是一个有向无环图。一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，那么我们对所有的活动进行先后顺序的排序，排序好的活动就是拓扑排序

为什么这个题可以使用拓扑排序：

这里可以看做多叉树层次遍历从下向上遍历，我们先尽可能多的遍历根节点也就是入为 1 的节点，将这写节点放入 queue 中，就比如上图图 2 的 node 0,2,3 ，并且对 0 ，2 ，3所连 node 的入度进行 –

然后往上走用同样的方法再遍历入度为 1 的 node ，这时候也只剩下 node 1 了，所以两层就遍历完了

但是如果我们先对 node 1 进行层次遍历，将 node 1 放在下面或者中间的位置，那么最后由下向上生成的图就是层数为 3 的树

2，拓扑排序和 BFS 的区别

拓扑排序每一次处理的是多个入度为 0 的点，也就是说在剥的时候是一剥剥一层，所以每一次 pop 节点的时候 pop 的是一层的节点

BFS 从某个点出发一次只处理和这个节点相邻的节点，也就是一次只处理一个节点

3.为什么最后 count 不能为 n-3

因为当 count = n-3 时说明还剩下 3 个点没有处理，如果剩下 3 个点其实还是有一层可以剥的

但是只剩下 2 个或者 1 个的时候就不能再剥了

易错点：

一开始我以为是层数问题，求哪个节点的层数最少，但是这个题虽然说树是一个无向图，但是我们在遍历的时候只能向下遍历，不能向上遍历，只不过这个图是一个多叉树罢了，

2.7.2 代码实现

1.拓扑排序

class Solution {
  public:
  vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) 
  {
    if (n==1) return {0};
    if (n==2) return {0,1};

    vector<vector<int>>next(n);
    vector<int>degree(n);

    for (auto edge: edges)
    {
      int a = edge[0], b = edge[1];
      degree[a]++;
      degree[b]++;
      next[a].push_back(b);
      next[b].push_back(a);
    }

    queue<int>q;
    vector<int>visited(n);
    for (int i=0; i<n; i++)
    {
      if (degree[i]==1)
        q.push(i);
    }

    int count = 0;
    while (!q.empty())
    {
      int len = q.size();
      while (len--)
      {
        int cur = q.front();
        q.pop();
        count++;
        visited[cur] = 1;
        for (int nxt: next[cur])
        {
          degree[nxt]--;
          if (degree[nxt]==1)
            q.push(nxt);
        }                
      }
      if (count==n-1 || count==n-2)
        break;
    }

    vector<int>rets;
    while (!q.empty())
    {
      rets.push_back(q.front());
      q.pop();                
    }

    return rets;

  }
};
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
50
51
52
53
54
55
56
57
58
59

2.暴力

class Solution {
  public:
  vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    // 最小高度树：从一个点向外扩散，层数最小则高度最小
    // A
    vector<vector<int>> A(n,vector<int>(n,0));
    vector<int> res;
    int min_val = INT_MAX;
    for(int i = 0;i<edges.size();i++){
      int a = edges[i][0];
      int b = edges[i][1];
      A[a][b] = 1;
      A[b][a] = 1;
    }
    // 遍历每个节点，计算他们的深度
    int max_val = INT_MAX;
    for(int i = 0;i<n;i++){
      queue<int> que;
      que.push(i);
      int deep = 0;
      vector<bool> visited(n,false);
      while(!que.empty()){
        int size = que.size();
        deep++;
        for(int i = 0;i<size;i++){
          int cur = que.front();
          que.pop();
          visited[cur] = true;
          for(int j = 0;j<n;j++){
            if(A[cur][j]&&!visited[j]) que.push(j);
          }
        }
      }
      if(deep==max_val){
        res.push_back(i);
      }else if(deep<max_val){
        res.clear();
        res.push_back(i);
        max_val = deep;
      }
    }
    return res;

  }
};
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

2.11_2400. 恰好移动 k 步到达某一位置的方法数目

2.11.1 算法概述

这个题和其他题的不同之处就在于这个题可以向一个负方向走，所以在 dfs 中 cur 的值就有可能是负数，但是 dp 的下标是从 0 开始的，所以用 [0-1000] 代表 [-1000~-1] 的这个范围

那么 cur 的每一个值都要 +2000

2.11.2 代码实现

class Solution {
  public:
  const int mod = 1e9+7;
  int dfs(int cur,int endPos,int rest,vector<vector<int>>& dp){
    if(rest==0){
      if(cur==endPos) return 1;
      return 0;
    }
    if(abs(cur-endPos)>rest) return 0;
    if(dp[cur+2000][rest]!=-1) return dp[cur+2000][rest];
    dp[cur+2000][rest] = 0;
    // 返回值
    if(cur+1<=2000){ // 向右走
      dp[cur+2000][rest]+=dfs(cur+1,endPos,rest-1,dp);
      dp[cur+2000][rest]%=mod;
    }
    if(cur-1>=-1000){ // 向左走
      dp[cur+2000][rest]+=dfs(cur-1,endPos,rest-1,dp);
      dp[cur+2000][rest]%=mod;
    }
    // dp[cur][rest] 
    return dp[cur+2000][rest];
  }
  int numberOfWays(int startPos, int endPos, int k) {
    vector<vector<int>> dp(4010,vector<int>(k+1,-1));
    return dfs(startPos,endPos,k,dp);
  }
};
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