2022.07.14_Daily Question

797. 所有可能的路径

题目描述

给你一个有 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）

 

Related Topics

• 深度优先搜索
• 广度优先搜索
• 图
• 回溯

coding

class Solution {
    
        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    
            List<List<Integer>> res = new ArrayList<>();
            int index = 0;
            List<Integer> record = new ArrayList<>();
            // 从 0 出发
            record.add(0);
            dfs(graph, res, index, record);
            return res;
        }

        private void dfs(int[][] graph, List<List<Integer>> res, int index, List<Integer> record) {
    
            // 到 n - 1 over
            if (index == graph.length - 1) {
    
                // The current record is added to the path of res
                res.add(new ArrayList<>(record));
                return;
            }
            for (int i = 0; i < graph[index].length; i++) {
    
                // Add a pointer to the node under
                record.add(graph[index][i]);
                // Add the current node as the index of the next node location, Starting from the next node to continue dfs
                dfs(graph, res, graph[index][i], record);
                // 回溯
                // 【PS】: list.remove(int 索引) 
                // list.remove(new Integer(list 集合中的元素))
                record.remove(new Integer(graph[index][i]));
            }
        }
    }