🚧 797.所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例
示例 1：
1
2
3
| 输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
|
示例 2：
1
2
| 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
|
第i行的所有元素代表从第i个节点出发，能够到达的所有节点
思路
基本思想
为了得到所有的路径，势必要进行搜索，从0号节点出发，最终到达n-1号节点就形成了一条路径，相当于是对给定的 二维数组进行遍历
所以使用了回溯的思想，在一层中遍历当前节点能到达的所有节点，选择其中的一个节点到达下一层，从这个新选择的节点出发，有可以到达一些节点，继续选择一个向下一层，最终到达n-1层说明形成了一个完整的路径，此时保存此路径，之后向上回溯，重新选择一个节点
当前层的所有节点遍历完成之后，向上回溯一层，重新选择一个没选择过的节点，然后继续向下，就这样不停地回溯再向下，最终搜索出所有可能的路径
执行流程
- 从节点0出发，遍历其能到达的所有节点
- 选择其中的一个节点，继续向下
- 当到达最终的n-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
| class Solution {
public:
//如何遍历给定的有向无环图，也会形成一个搜索树，一层是对应的一个节点能到达的其所有节点
//一列是从一个节点到另一个节点，就是回溯法的简单改造
vector<int> path;
vector<vector<int>> res;
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//从0节点出发向后遍历，搜索树的第一层就是所有0号节点
path.push_back(0);
dfs(graph,0);
return res;
}
void dfs(vector<vector<int>>& graph,int node){
//当前形成路径的尾部是最后一个节点，也就是终点
if(node==graph.size()-1){
res.push_back(path);
return;
}
//在本层中遍历当前节点node能到达的所有其他节点
for(int i=0;i<graph[node].size();++i){
//从node出发，到达当前的graph[node][i]节点上，然后继续向下
path.push_back(graph[node][i]);
dfs(graph,graph[node][i]);
//当前节点遍历完了，从node出发换一个到达节点
path.pop_back();
}
}
};
|
总结
