> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/601-800/797.-suo-you-ke-neng-de-lu-jing.md).

# 797.所有可能的路径

<https://leetcode-cn.com/problems/all-paths-from-source-to-target/>

## 一、dfs

因为是有向无环图，所以从起点直接dfs每个邻节点，回溯中记录路径，直到终点记录路径即可，**不用考虑重复访问**

```python
class Solution:
    def allPathsSourceTarget(self, graph):
        res = []
        n = len(graph)

        def dfs(now, path):
            path.append(now)    #尝试在路径中加入当前节点
            if now == n-1:    #递归出口1：遍历到终点。
                # 记录该路径，并弹出
                res.append(list(path))
                path.pop()
                return
            # 递归遍历每个相邻节点
            for v in graph[now]:
                dfs(v, path)
            path.pop()      #有加入就要有弹出
            return      #递归出口2：全部相邻节点遍历完（如果是空返回可以省略）

        dfs(0, [])
        return res
```

## 改进：

递归中不直接修改path，省去很多“恢复现场”的工作

```python
class Solution:
    def allPathsSourceTarget(self, graph):
        res = []
        n = len(graph)

        def dfs(now, path):
            if now == n - 1:  # 递归出口1：遍历到终点。
                res.append(list(path))
                return
            # 递归遍历每个相邻节点
            for v in graph[now]:
                dfs(v, path+[v])

        dfs(0, [0])		#初始默认起点在路径中
        return res
```