所有可能的路径

这题的重点不是“找一条路”，而是“把从起点到终点的所有合法路径都枚举出来”，所以它天然就是 DFS + 回溯题。

问题描述

LeetCode 797 - 所有可能的路径

给定一个有向无环图（DAG），找出从节点0到节点n-1的所有可能路径。

输入: graph = [[1,2],[3],[3],[]]
输出: [[0,1,3],[0,2,3]]

图示:
    0 → 1
    ↓   ↓
    2 → 3

解题思路

• 回溯算法：使用DFS遍历所有路径
• 路径记录：记录当前路径
• 终点判断：到达n-1时记录路径
• 无需visited：DAG保证无环

为什么这里不用 visited

因为题目明确给的是 DAG。
既然无环，从当前点往后走就不可能绕回来，所以当前路径天然不会重复撞回自己。

这也是它比一般图回溯更简单的原因。

Go 代码

Go 实现

func allPathsSourceTarget(graph [][]int) [][]int {
    n := len(graph)
    target := n - 1
    result := [][]int{}
 
    var dfs func(int, []int)
    dfs = func(node int, path []int) {
        if node == target {
            // 复制路径
            pathCopy := make([]int, len(path))
            copy(pathCopy, path)
            result = append(result, pathCopy)
            return
        }
 
        for _, neighbor := range graph[node] {
            dfs(neighbor, append(path, neighbor))
        }
    }
 
    dfs(0, []int{0})
    return result
}

易错点

这题最容易错的地方，不是 DFS，而是结果路径的拷贝。

• 到终点时必须拷贝当前路径，不能直接把同一个切片引用塞进答案。
• 如果改成手动 append / pop 的回溯写法，记得状态要恢复。
• DAG 不需要 visited，但一般图的“所有路径”问题就不能这么直接套。

复杂度分析

指标	复杂度	说明
时间复杂度	O(2^V × V)	最多2^V条路径，每条路径长度V
空间复杂度	O(V)	递归栈深度

相关变体

相关主题

• DFS - 基于DFS
• 回溯算法 - 回溯思想
• 图算法 - 返回图算法总览

---

返回：图算法 | 算法学习导航