LeetCode 797. 所有可能的路径

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 微软 网易
标签
深度优先搜索 广度优先搜索 回溯 图

题目描述

✅ 797. 所有可能的路径

image-20260928224832710

image-20260928224832711

image-20260928224832712

题意分析

给定有向无环图，graph[i] 列出节点 i 的所有出边终点。要求返回从 0 到 n-1 的全部路径，顺序不限。不同路径可以在中途汇合并共用后续节点，因此要保留每条路径的完整前缀。

解法：DFS 回溯构造全部路径

核心思路

[!blue]

用 path 保存从 0 到当前节点 node 的完整路径，dfs(node) 尝试把它继续延长。对 graph[node] 中的每个邻居，先把邻居加入路径，再递归搜索，返回时删除刚加入的节点，恢复本层原来的路径。

到达 n-1 时，当前路径已经是一条答案，复制保存后返回。必须保存副本，因为工作路径随后还会被其他分支追加和撤销；如果保存同一个列表或切片，它的内容可能随着回溯发生变化。

每一步都沿真实出边扩展，所以收集到的路径一定合法；任意一条从起点到终点的路径，也都对应搜索中依次选择这些出边的分支，因此不会遗漏。无环保证一条路径不会重复经过节点，深度最多为节点数，搜索一定结束。

这里不能用永久的全局 visited 跳过已经访问过的节点。同一个节点从不同前缀到达时，会形成不同的完整路径，必须分别继续搜索；图本身无环，已经提供了避免无限递归的保证。

解题步骤

  • 把 0 加入空路径，调用 dfs(0)。
  • 若当前节点等于 n-1，将路径副本加入结果并返回。
  • 否则遍历所有出边，对每个邻居依次执行加入路径、递归、移出路径。
  • 搜索结束返回结果列表；如果起点无法到达终点，结果为空。

没有出边的节点不一定是指定终点。到达其他死路时，循环自然结束并回退，不能把这种未完成路径加入答案。

代码实现

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        path.add(0);
        dfs(0, graph, path, res);

        return res;
    }

    private void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> res) {
        if (node == graph.length - 1) {
            // 复制当前路径，兄弟分支会继续修改工作缓冲
            res.add(new ArrayList<>(path));

            return;
        }

        for (int next : graph[node]) {
            path.add(next);
            dfs(next, graph, path, res);
            // 分支结束撤销邻居，保留父层原有路径
            path.remove(path.size() - 1);
        }
    }
}

func allPathsSourceTarget(graph [][]int) [][]int {
    res := make([][]int, 0)
    path := []int{
        0,
    }

    var dfs func(node int)
    dfs = func(node int) {
        if node == len(graph)-1 {
            copyPath := make([]int, len(path))
            // 复制当前路径，兄弟分支会继续修改工作缓冲
            copy(copyPath, path)
            res = append(res, copyPath)
            return
        }

        for _, next := range graph[node] {
            path = append(path, next)
            dfs(next)
            // 分支结束撤销邻居，保留父层原有路径
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return res
}

复杂度分析

  • 时间复杂度：最坏为 $O(n2^n)$。DAG 中的路径数量可能达到指数级，每条答案还需要复制最多 $n$ 个节点，因此不能按普通“每个节点只访问一次”的 DFS 估算。
  • 空间复杂度：不计输出为 $O(n)$，来自当前路径和递归栈；输出本身最坏占 $O(n2^n)$。

关键点总结

[!green]

  • 叶子不一定是指定终点，必须按编号判断。
  • 结果保存副本，工作路径继续回溯。

易错点总结

[!yellow]

  • 保存路径引用会被后续撤销改变。
  • 进入邻居前不加入路径，会漏掉节点。
  • 永久标记汇合节点，会误剪其他合法路径。

相似题目

题目 难度 关联与区别
126. 单词接龙 II 困难 同样输出从起点到终点的多条路径，原题只要最短路径，本题DAG中所有路径都要保留。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/83983540
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！