# LeetCode Problems #797

xiaoxiao2021-03-01  6

# #797. All Paths From Source to Target

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.

class Solution: def allPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """

若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

#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