编程学习笔记(LeetCode-797. 所有可能的路径)

<797> 所有可能的路径

• 问题重述：

  给定一个有 \(n\) 节点的 有向无环图(DAG) ，现需要你找出所有从节点 \(0\) 到节点 \(n-1\) 的路径，并且输出（路径顺序任意）。

  在本题中，有向无环图，用一个二维数组表示，第i个数组中的单元都表示有向图中i号节点所能到达的下一些节点，空就是没有下一个结点了。

例如：

1. 对于二维数组

graph = [
    [1,2],      //0号节点出发能到的节点
    [3],        //1号节点出发能到的节点
    [3],        //2号节点出发能到的节点
    []          //3号节点出发能到的节点
]

有图：

graph LR 0 --> 1 0 --> 2 1 --> 3 2 --> 3

2. 对于二维数组

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)\)
  因为返回值不计入空间复杂度，那么此处主要是执行栈空间的开销。