1. 题目描述

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

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 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]]

提示：

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i（即不存在自环）
• graph[i] 中的所有元素 互不相同
• 保证输入为 有向无环图（DAG）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

       第一感是可达性（reachability）问题，可以用深度优先搜索。

        但是题目并不是只是要求判断可达性，而是要找出所有的路径，所以可以看作是路径遍历搜索问题。仍然可以用深度优先搜索来处理，但是不是已找到目标点就结束，而是必须遍历完整个图找出所有可能路径。在搜索过程中必须记忆并最终输出所有路径。

        但是在代码实现方面有一些小的细节需要注意。参见后面的描述。

 3. 一个代码问题：TypeError: 'NoneType' object is not subscriptable

        在代码实现中碰到一个问题，报错信息为'NoneType' object is not subscriptable。

        原始代码如下：

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        paths = []
        N     = len(graph)
        print(N, graph)
        def dfs(path):
            nonlocal paths 
            nonlocal N
            nonlocal graph
            print('dfs(): ', path, graph)
            # Traverse all neighbor nodes of the last node except those already in path
            for node in graph[path[-1]]:
                print('dfs(): ', path, graph[path[-1]], node)
                if node == N-1:
                    # One path found
                    paths.append(path.append(node))
                else:
                    if node not in path:
                        dfs(path.append(node))
        dfs([0])
        return paths

if __name__ == '__main__':
    sln = Solution()
    
    graph = [[1,2],[3],[3],[]]               
    print(sln.allPathsSourceTarget(graph))     
    
    graph = [[4,3,1],[3,2,4],[3],[4],[]]
    print(sln.allPathsSourceTarget(graph))

        看打印信息，百思不得其解。。。 最后终于明白了。伙伴们，你看出来了吗？

        有兴趣的小伙伴可以先看看能不能找出以上代码中的错误并订正，然后再看下面的正确解答。 

4. 代码实现

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        paths = []
        N     = len(graph)
        print(N, graph)
        def dfs(path):
            nonlocal paths 
            nonlocal N
            nonlocal graph
            # print('dfs(): ', path, graph)
            # Traverse all neighbor nodes of the last node except those already in path
            for node in graph[path[-1]]:
                if node == N-1:
                    # One path found
                    paths.append(path+[node])
                else:
                    if node not in path:
                        dfs(path+[node])
        dfs([0])
        return paths

if __name__ == '__main__':
    sln = Solution()
    
    graph = [[1,2],[3],[3],[]]               
    print(sln.allPathsSourceTarget(graph))     
    
    graph = [[4,3,1],[3,2,4],[3],[4],[]]
    print(sln.allPathsSourceTarget(graph))

        执行用时：48 ms, 在所有 Python3 提交中击败了53.25%的用户

        内存消耗：16.3 MB, 在所有 Python3 提交中击败了34.41%的用户

        回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)