1.题目

给你一个有 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.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即不存在自环）
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图（DAG）

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/all-paths-from-source-to-target

2.思路

（1）图的遍历
思路参考图论基础。

3.代码实现（Java）

//思路1————图的遍历
class Solution {

    //记录所有路径
    List<List<Integer>> res = new LinkedList<>();
    
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        //记录中间结果
        LinkedList<Integer> path = new LinkedList<>();
        traverse(graph, 0, path);
        return res;
    }

    //图的遍历框架(输入的图是无环的，故不需要 visited 数组辅助)
    public void traverse(int[][] graph, int s, LinkedList<Integer> path) {
        //将节点 s 加入到 path 中
        path.add(s);
        int n = graph.length;
        if (n - 1 == s) {
            //到达终点，则将当前得到的一条路径 path 加入到 res 中
            res.add(new LinkedList<>(path));
            path.removeLast();
            return;
        }
        //遍历当前节点的每个相邻节点
        for (int v : graph[s]) {
            traverse(graph, v, path);
        }
        path.removeLast();
    }
}

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！