代码随想录算法训练营第四十一天|图论基础、深度优先搜索理论基础、98. 所有可达路径、797. 所有可能的路径

图论基础

图的种类：有向图 和 无向图，加权有向图， 加权无向图

无向图中有几条边连接该节点，该节点就有几度。

在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。

图的遍历方式：

• 深度优先搜索（dfs）
• 广度优先搜索（bfs）

 深度优先搜索（DFS）、广度优先搜索（BFS）、并查集、拓扑排序、最小生成树系列、最短路算法系列...

深度优先搜索理论基础

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

DFS（深度优先搜索）：

往一个方向搜索，不到黄河不回头。
从1到6的第一条路径如下：

此时我们找到了节点6，（遇到黄河了，是不是应该回头了），那么应该再去搜索其他方向了。 

路径2撤销了，改变了方向，走路径3（红色线）， 接着也找到终点6。 那么撤销路径2，改为路径3，在dfs中其实就是回溯的过程（这一点很重要，很多录友不理解dfs代码中回溯是用来干什么的）

又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图四中，路径4撤销（回溯的过程），改为路径5。

又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图五，路径6撤销（回溯的过程），改为路径7，路径8 和 路径7，路径9， 结果发现死路一条，都走到了自己走过的节点。

那么节点2所连接路径和节点3所链接的路径 都走过了，撤销路径只能向上回退，去选择撤销当初节点4的选择，也就是撤销路径5，改为路径10 。 如图图六：

其他节点的过程省略，总体来说的两个步骤就是：

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

因为dfs搜索向一个方向，并且需要回溯，所以可以用递归方式来实现。

void dfs(参数) {处理节点dfs(图，选择的节点); // 递归回溯，撤销处理结果
}

回溯算法，其实就是dfs的过程：

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

深搜三部曲：

1. 确定递归函数；2. 确认终止条件； 3. 处理目前搜索节点出发的路径

98. 所有可达路径

实现这两个图的存储方式：邻接矩阵 邻接表

邻接矩阵：

vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
// 输入m个边，构造方式如下：
while (m--) {cin >> s >> t;// 使用邻接矩阵 ，1 表示 节点s 指向 节点tgraph[s][t] = 1;
}

邻接表： 数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表
// 输入m个边，构造方式如下：
while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);
}

1. 确认递归函数：

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

2. 确认终止条件：

当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。

// 当前遍历的节点x 到达节点n 
if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;
}

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

for(int i=1; i<=n; i++){if(graph[x][i] == 1) {path.push_back(i);dfs(graph, i, n);path.pop_back(i);}
}

所以本题使用ACM模式写出来就是：

#include <iostream>
#include <vector>
#include <list>
using namespace std;
vector<vector<int>> result;
vector<int> path;//void dfs(const vector<vector<int>>& graph, int x, int n){void dfs(const vector<list<int>>& graph, int x, int n){//当前遍历的节点x到达节点nif(x==n){result.push_back(path);return;}// for(int i=1; i<=n; i++){//     if(graph[x][i]==1){ //找到x链接的节点//         path.push_back(i);//         dfs(graph, i, n);//         path.pop_back();//     }// }for(int i:graph[x]){path.push_back(i);dfs(graph, i, n);path.pop_back();}
}
int main(){int n, m, s, t;cin>>n>>m;//vector<vector<int>> graph(n+1, vector<int>(n+1, 0));vector<list<int>> graph(n+1);while(m--){cin>>s>>t;//graph[s][t] = 1;graph[s].push_back(t);}path.push_back(1);//无论什么路径已经是从0节点出发dfs(graph, 1, n);if(result.size()==0) cout<<-1<<endl;for(const vector<int>&pa : result){for(int i=0; i<pa.size()-1; i++){cout<<pa[i]<<" ";}cout<<pa[pa.size()-1]<<endl;}
}

797. 所有可能的路径

class Solution {
public:vector<vector<int>> result;vector<int> path;void dfs(vector<vector<int>>& graph, int x, int n){if(x==n){result.push_back(path);return;}// for(int i=1; i<=n; i++){//     if(graph[x][i]==1){//         path.push_back(i);//         dfs(graph, i, n);//         path.pop_back();//     }// }for (auto& y : graph[x]) {path.push_back(y);dfs(graph, y, n);path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);dfs(graph, 0, graph.size()-1);return result;}
};