编程学习笔记(LeetCode-797. 所有可能的路径)
<797> 所有可能的路径
- 问题重述：
给定一个有 \(n\) 节点的 有向无环图(DAG) ，现需要你找出所有从节点 \(0\) 到节点 \(n-1\) 的路径，并且输出（路径顺序任意）。
在本题中，有向无环图，用一个二维数组表示，第i个数组中的单元都表示有向图中i号节点所能到达的下一些节点，空就是没有下一个结点了。
例如：
- 对于二维数组
graph = [
[1,2], //0号节点出发能到的节点
[3], //1号节点出发能到的节点
[3], //2号节点出发能到的节点
[] //3号节点出发能到的节点
]
有图：
graph LR 0 --> 1 0 --> 2 1 --> 3 2 --> 3- 对于二维数组
graph = [
[4,3,1], //0号节点出发能到的节点
[3,2,4], //1号节点出发能到的节点
[3], //2号节点出发能到的节点
[4], //3号节点出发能到的节点
[] //4号节点出发能到的节点
]
有图：
graph TB 0 --> 4 0 --> 3 0 --> 1 1 --> 3 1 --> 2 1 --> 4 2 --> 3 3 --> 4注： 在图中，若规定了 a → b 那么你就不能 b → a。
示例1：
输入： graph = [[1,2],[3],[3],[]]
输出： [[0,1,3],[0,2,3]]
解释： 有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例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]]
示例 3：
输入： graph = [[1],[]]
输出： [[0,1]]
示例 4：
输入： graph = [[1,2,3],[2],[3],[]]
*输出： [[0,1,2,3],[0,2,3],[0,3]]
示例 5：
输入： graph = [[1,3],[2],[3],[]]
输出： [[0,1,2,3],[0,3]]
你可以假定：
- \(n == graph.length\)
- \(2 \leqslant n \leqslant 15\)
- \(0 \leqslant graph[i][j] < n\)
- \(graph[i][j] \neq i\)（即，不存在自环）
- \(graph[i]\) 中的所有元素 互不相同
- 保证输入为 有向无环图（DAG）
问题解答：
在一张有向图中，要考究从某个节点(0号节点)出发，是否能到另一个节点(n-1号节点)，那么就是要尝试遍历所有路径，看是否能到达目标节点。而遍历一张图的所有路径一般的方法有：广度优先遍历（BFS） 和 深度优先遍历（DFS）。
那么对于本题，经过分析，我们易知，需要遍历所有的路径，那么对于全路径遍历的情况，无论是采用DFS或是BFS，性能相当，所以这里就采用深度优先遍历的方法。
又因为题目给定的是一个 有向且无环 的图（DAG），因此在深度遍历搜索的过程中不会反复地遍历同一个节点，因此无需判断当前的点是否遍历过。
对于 深度遍历搜索（DFS），实现它的方法就是用 栈（Stack） ，从起点出发，使用栈去记录路径上的点，当发现可以遍历到目标节点的时候，就将栈中记录的路径加入到答案集中。
- 例如之前提到的一张图：
graph = [
[4,3,1], //0号节点出发能到的节点
[3,2,4], //1号节点出发能到的节点
[3], //2号节点出发能到的节点
[4], //3号节点出发能到的节点
[] //4号节点出发能到的节点
]
我们把它所有可能的路径都画出来，那么可以画出如下的路线图，其实他就是一颗解答树，我们就是要想办法用程序去遍历这颗解答树：
graph TD start(0) level1a([4]) level1b(3) level1c(1) level2a([4]) level2b(3) level2c(2) level2d([4]) level3a([4]) level3b(3) level4a([4]) start --> level1a start --> level1b start --> level1c level1b --> level2a level1c --> level2d level1c --> level2b level1c --> level2c level2b --> level3a level2c --> level3b level3b --> level4a正如前面所说，遍历题目所给的有向无环图，其实就是要我们采用何种方法去遍历这颗解答树，此处我们采用 深度优先（DFS） 的策略去遍历这颗解答树。
在用程序解答这棵解答树的时候，我们需要声明一个栈stack，用来存储当前遍历路径节点，但是为了省事，这里我直接使用程序的 执行栈 ，说人话就是使用 递归函数 。那么程序如下所示（采用C++语言）：
采用递归的方法，实现DFS（C++）：
class Solution {
public:
vector<vector<int> > result; //用于存储返回结果
vector<int> cur_road; //用于记录当前路径
void dfs(vector<vector<int>>& graph, int n_1){
//判断当前路径的最后一个节点是否是目标节点
//如果是则记录并返回
//否则继续遍历
if(this->cur_road.back() == n_1){
this->result.push_back(this->cur_road);
return;
}
//题目给定的是一个 有向无环图（DAG），
//因此在深度遍历搜索的过程中不会反复地遍历同一个节点，
//因此无需判断当前的点是否遍历过。
for(int var: graph[this->cur_road.back()]){ //遍历当前节点的所有子节点
//开始解答其中一个子节点
this->cur_road.push_back(var);
dfs(graph, n_1);
//遍历完之后要记得 pop 出去，
//表示解答树中的当前节点以及它的所有后代已经遍历完了，
//要开始解答兄弟节点了，当解答完所有兄弟节点，就返回到父亲节点
this->cur_road.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//初始化全局变量
this->cur_road.push_back(0);
//开始递归遍历
dfs(graph, graph.size()-1);
//返回结果
return this->result;
}
};
时空复杂度分析：
- 时间复杂度： \(O(n \times 2^n)\)
在最坏的条件下，遍历时，每一个点都往编号比他大的点走，此时遍历的路径数为 \(O(2^n)\) ，路径长度为 \(O(n)\) ，所以时间复杂度为：\(O(n \times 2^n)\) 。
- 空间复杂度： \(O(n)\)
因为返回值不计入空间复杂度，那么此处主要是执行栈空间的开销。