代码随想录算法训练营Day56|所有可达路径、797.所有可能的路径

所有可达路径

98. 所有可达路径 (kamacoder.com)

深度优先搜索，和之前的回溯题类似。

#include <iostream>
#include <vector> 
using namespace std;// 定义一个二维向量来存储所有可能的路径
vector<vector<int>> paths;
// 定义一个向量来存储当前路径
vector<int> path;// 定义深度优先搜索函数
void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达节点n，将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历所有可能的下一个节点for (int i = 1; i <= n; i++) {// 如果节点x和节点i之间有边（即连通）if (graph[x][i] == 1) {// 将节点i添加到当前路径path.push_back(i);// 递归地继续搜索从节点i开始的路径dfs(graph, i, n);// 回溯，移除节点i，尝试其他可能的路径path.pop_back();}}
}int main() {int N, M; // N表示节点数量，M表示边的数量cin >> N >> M; // 输入节点数量和边的数量// 创建一个(N+1) x (N+1)的二维向量，初始化所有值为0vector<vector<int>> graph(N + 1, vector<int>(N + 1, 0));int s, t;while (M--) { // 循环M次，输入每条边的两个节点cin >> s >> t;graph[s][t] = 1; // 表示节点s和节点t之间有边，即连通}// 从节点1开始搜索，将节点1添加到当前路径path.push_back(1);dfs(graph, 1, N); // 调用DFS函数搜索所有路径// 如果没有找到路径，输出-1if (paths.size() == 0)cout << -1 << endl;// 输出所有找到的路径for (auto x : paths) {for (int i = 0; i < x.size() - 1; i++) {cout << x[i] << " ";}cout << x[x.size() - 1] << endl;}
}

在构建图是，读入所有边，时间复杂度为O(M)，在DFS是，最坏情况需要访问图中的每个节点和每天便，DFS的时间复杂度为O(N+M)。总的时间复杂度为O(N+M)。

空间复杂度，用邻接矩阵来存储graph信息需要（N+1）^2(从0到N+1的矩阵)，paths在图全连接的情况下，可能要存储2^(N-1)条路(1-N)，path为O(N)，空间复杂度为O(2^(N-1))。

邻接链表参考

代码随想录 (programmercarl.com)

邻接数组也可以自己写写看。

所有可能的路径

797. 所有可能的路径 - 力扣（LeetCode）

上题的核心代码，代码如下，分析基本和上题相同。

class Solution {
public:// 定义一个向量来存储当前路径vector<int> path;// 定义一个二维向量来存储所有可能的路径vector<vector<int>> paths;// 定义深度优先搜索函数void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达目标节点n，将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历当前节点的所有相邻节点for (int i = 0; i < graph[x].size(); i++) {// 将相邻节点添加到当前路径path.push_back(graph[x][i]);// 递归地继续搜索从相邻节点开始的路径dfs(graph, graph[x][i], n);// 回溯，移除刚刚添加的节点，以便尝试其他路径path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {// 目标节点是图的最后一个节点 graph.size() - 1int n = graph.size() - 1;// 从源节点0开始，将源节点添加到当前路径path.push_back(0);// 调用DFS函数搜索所有路径dfs(graph, 0, n);// 返回找到的所有路径return paths;}
};