问题描述：
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
样例:
Example: Input: [[1,2], [3], [3], []] Output: [[0,1,3],[0,2,3]] Explanation: The graph looks like this: 0--->1 | | v v 2--->3 There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.Note:
The number of nodes in the graph will be in the range [2, 15].You can print different paths in any order, but you should keep the order of nodes inside one path.问题分析：
本题难度为Medium！已给出的函数定义为：
class Solution: def allPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """其中graph为一个二维数组，返回值为一个存储列表单元的列表；
本题是找出从源结点0到目标结点N-1的所有路径。
算法如下：
从源结点0出发，记录到path列表中，即path=[0]
调用递归函数dfs，cur=0，des=N-1，path=[0]
若cur==des，则将path添加到result中
否则若cur有出度，对于每一个出度结点each：
复制路径cp_path=path，将每一个出度结点添加到复制的路径中
调用递归函数dfs，cur=each，des=N-1，cp_path
result即为存储的所有路径
代码实现：
#coding=utf-8 class Solution: def allPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """ def dfs(cur, des, path): if cur==des: #到达目标点 result.append(path) elif len(graph[cur])!=0: #未到达目标点，且cur点出度不为0，进行递归 for each in graph[cur]: #对每个出度进行递归 cp_path=path.copy() #复制临时路径 cp_path.append(each) dfs(each,des,cp_path) result=[] dfs(0,len(graph)-1,[0]) return result此算法可以在Leetcode上Accrpted，但只能处理有向无环图dag；若遇到有向有环图，则会陷入死循环导致：RecursionError: maximum recursion depth exceeded in comparison。
改进算法代码如下：
添加一个visited列表记录访问过的结点，从而防止递归陷入死循环。
#coding=utf-8 class Solution: def allPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """ def dfs(cur, des, path, visited): if cur==des: #到达目标点 result.append(path) elif len(graph[cur])!=0: #未到达目标点，且cur点出度不为0，进行递归 for each in graph[cur]: #对每个出度进行递归 if visited[each]==0: cp_path=path.copy() #复制临时路径 cp_path.append(each) #添加结点 cp_visited=visited.copy() #复制临时访问列表 cp_visited[each]=1 #标记结点 dfs(each,des,cp_path,cp_visited) result=[] visited=[0 for i in range(len(graph))] visited[0]=1 dfs(0,len(graph)-1,[0],visited) return result
