图论第一天|深度优先搜索理论基础、广度优先搜索理论基础、797.所有可能的路径

深度优先搜索理论基础

文档讲解 ：

1. 代码随想录 - 深度优先搜索理论基础
2. Hello 算法 9.3 图的遍历

状态：开始学习。

dfs（深度优先搜索）与bfs（广度优先搜索）区别

• dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。（实现机制类似栈，后入先出）
• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。（实现机制类似队列，先入先出）
  

dfs搜索过程

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。

dfs三部曲

1. 确认递归函数，参数

   vector<vector<int>> result; // 保存符合条件的所有路径
   vector<int> path; // 起点到终点的路径
   void dfs (图，目前搜索的节点)  
   1
   2
   3

2. 确定终止条件

   if (终止条件) {
       存放结果;
       return;
   }
   1
   2
   3
   4

3. 处理目前搜索节点出发的路径

   for (选择：本节点所连接的其他节点) {
       处理节点;
       dfs(图，选择的节点); // 递归
       回溯，撤销处理结果
   }
   1
   2
   3
   4
   5

广度优先搜索理论基础

文档讲解 ：

1. 代码随想录 - 广度优先搜索理论基础
2. Hello 算法 9.3 图的遍历

状态：开始学习。

bfs的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

bfs搜索过程

bfs代码框架

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> 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]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

797.所有可能的路径

文档讲解 ：代码随想录 - 797.所有可能的路径
状态：开始学习。

dfs

1. 确认递归函数，参数

   vector<vector<int>> result; // 收集符合条件的路径
   vector<int> path; // 0节点到终点的路径
   // x：目前遍历的节点
   // graph：存当前的图
   void dfs (vector<vector<int>>& graph, int x) 
   1
   2
   3
   4
   5

2. 确认终止条件

   // 要求从节点 0 到节点 n-1 的路径并输出，所以是 graph.size() - 1
   if (x == graph.size() - 1) { // 找到符合条件的一条路径
       result.push_back(path); // 收集有效路径
       return;
   }
   1
   2
   3
   4
   5

3. 处理目前搜索节点出发的路径

   for (int i = 0; i < graph[x].size(); i++) { // 遍历节点n链接的所有节点
      path.push_back(graph[x][i]); // 遍历到的节点加入到路径中来
      dfs(graph, graph[x][i]); // 进入下一层递归
      path.pop_back(); // 回溯，撤销本节点
   }
   1
   2
   3
   4
   5

本题代码（dfs）：

class Solution {
private:
    vector<vector<int>> result; // 收集符合条件的路径
    vector<int> path; // 0节点到终点的路径
    // x：目前遍历的节点
    // graph：存当前的图
    void dfs (vector<vector<int>>& graph, int x) {
        // 要求从节点 0 到节点 n-1 的路径并输出，所以是 graph.size() - 1
        if (x == graph.size() - 1) { // 找到符合条件的一条路径
            result.push_back(path);
            return;
        }
        for (int i = 0; i < graph[x].size(); i++) { // 遍历节点n链接的所有节点
            path.push_back(graph[x][i]); // 遍历到的节点加入到路径中来
            dfs(graph, graph[x][i]); // 进入下一层递归
            path.pop_back(); // 回溯，撤销本节点
        }
    }
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0); // 无论什么路径已经是从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
24
25

bfs

本题代码（bfs）：

class Solution {
    vector<vector<int>> result; // 收集符合条件的路径
    vector<int> path; // 0节点到终点的路径
    // graph：存当前的图
    // start: 起始路径
    void bfs(vector<vector<int>>& graph, vector<int> start) {
        queue<vector<int>> que; // 定义队列
        que.push(start); // 起始路径加入队列
        while (!que.empty()) { // 开始遍历队列里的元素；
            path = que.front(); // 从队列取元素（元素是路径）
            que.pop();
            int node = path.back(); //路径最后的节点
            if (node == graph.size() - 1) result.push_back(path); // 如果是最后一个节点，收集路径
            for (int i = 0; i < graph[node].size(); i++) { // 开始向图下一个节点遍历
                path.push_back(graph[node][i]); // 当前节点加入路径
                que.push(path); //搜索
                path.pop_back(); //回溯
            }
        }
    }
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        result.clear();
        path.clear();
        bfs(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
24
25
26
27
28