难度: Medium
给你一个有 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.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i（即不存在自环）graph[i] 中的所有元素 互不相同运行时间: 24 ms
内存: 17.4 MB
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
result=[]
path=[]
def dfs(graph: list[list[int]], root: int):
if root==len(graph)-1:
result.append(path[:])
return
for i in graph[root]:
path.append(i)
dfs(graph, i)
path.pop()
path.append(0)
dfs(graph, 0)
return result
这个题解使用了深度优先搜索（DFS）的思路来遍历有向无环图，找出所有从节点 0 到节点 n-1 的路径。具体思路如下： 1. 定义一个 dfs 函数，接受图 graph 和当前遍历的节点 root 作为参数。 2. 如果当前节点 root 等于图的最后一个节点（即 n-1），说明找到了一条完整的路径，将当前路径 path 添加到结果列表 result 中，并返回。 3. 遍历当前节点 root 的所有邻居节点 i，将节点 i 添加到当前路径 path 中，递归调用 dfs 函数，继续搜索下一个节点。 4. 在递归调用结束后，需要将节点 i 从路径 path 中移除，以便回溯到上一个节点，继续搜索其他可能的路径。 5. 在主函数中，先将起始节点 0 添加到路径 path 中，然后调用 dfs 函数开始搜索。 6. 最后返回结果列表 result，其中包含了所有从节点 0 到节点 n-1 的路径。
时间复杂度: O(V^2 + VE)，其中 V 为节点数，E 为边数。
空间复杂度: O(2^V * V)，其中 V 为节点数。
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
result = []
path = []
def dfs(graph: list[list[int]], root: int):
# 如果当前节点是最后一个节点，说明找到了一条完整路径
if root == len(graph) - 1:
result.append(path[:])
return
# 遍历当前节点的所有邻居节点
for i in graph[root]:
path.append(i)
dfs(graph, i)
path.pop() # 回溯，移除当前节点，继续搜索其他路径
path.append(0) # 起始节点为 0
dfs(graph, 0)
return result
在设计函数时传递图graph和当前节点root作为参数，可以使函数更加独立和模块化，增强代码的可读性和可维护性。这种方法有助于避免对全局变量的依赖，减少了不同部分之间的耦合，使得代码更容易理解和测试。此外，这样的设计也使得函数更加灵活，方便在不同的上下文中重用该函数，例如在同一个程序中对多个不同的图进行操作。
在递归过程中，path变量是被不断修改的，它用来存储当前的路径状态。如果直接将path添加到结果列表中，由于path是一个引用类型（列表），结果列表中的所有条目将指向同一个列表对象。当path在递归中被修改时，这些修改也会反映在已经存储在结果列表中的路径上。为了防止这种情况，使用path[:]进行深拷贝可以创建path当前状态的一个副本，这样每条路径都是独立的，互不影响。
回溯操作是通过在递归函数中，每当探索完一个节点后，将其从当前路径path中移除（即path.pop()操作），从而恢复到进入该节点前的状态。这样做可以让算法返回到上一个节点，继续探索其他可能的分支。回溯是深度优先搜索（DFS）的核心组成部分，使得通过只使用一个变量（path）来保存当前的状态，从而能够探索所有可能的路径。
是的，深度优先搜索（DFS）是通过系统调用栈来实现递归的，因此在节点数非常大的图中，递归深度过大可能会导致栈溢出。解决这个问题的一种方法是使用迭代的方法来实现深度优先搜索，例如使用显式栈来模拟递归调用的过程。另一种可能的解决方案是调整系统的栈大小限制，尽管这种方法可能不总是可行或推荐。另外，可以考虑使用广度优先搜索（BFS）或其他非递归算法来避免递归导致的问题。