难度：★★★☆☆
类型：图
方法：深度优先搜索

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 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]]

提示：

结点的数量会在范围 [2, 15] 内。
你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

解答

这个题是图遍历的经典题，可以使用深度优先搜索方法实现。

定义深度优先搜索函数get_paths_from()，函数的输入是起始节点的编号node，函数输出是以node节点为起点，到达终止节点dst_node的所有可能的路径，以嵌套列表的形式返回。函数完成的功能即为路径搜寻。

一般使用深度优先搜索函数会在入口处添加终止条件作为递归终点，这道题的终止条件即为到达终点。也就是说，当起点结点node即为终点结点dst_node时，说明成功到达终点，返回这条唯一的路径[[dst_node]]，注意这里要嵌套两层列表，因为内部的列表表示一条路径。

当输入节点node不满足递归终点时（也是大多数情况），我们就要搜寻node节点的下一跳结点，可能有多个，然后遍历这些下一跳结点next_node，以next_node为起点进行递归调用，获得以next_node为起点，到达dst_node的所有路线，然后将这些路线加到当前结点node上。

这里不用担心如果不存在node到dst_node的路线时的情况。因为如果不存在这些情况，路线列表是空的，不会进行遍历。

其他变量说明：
src_node，dst_node：起点和终点结点编号。
nums：图中结点总数。

class Solution(object):
    def allPathsSourceTarget(self, graph):
        nums = len(graph)
        src_node, dst_node = 0, nums - 1

        def get_paths_from(node):
            if node == dst_node:
                return [[dst_node]]
            ans = []
            for next_node in graph[node]:
                for path in get_paths_from(next_node):
                    ans.append([node] + path)
            return ans

        return get_paths_from(src_node)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析