LeetCode_图的遍历_中等_797. 所有可能的路径

﹏ヽ暗。殇╰゛Y 2023-10-06 22:41 17阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个有 n 个节点的 有向无环图（DAG），**请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）**

graph\[i\] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph\[i\]\[j\]存在一条有向边）。

**示例 1：**  
![在这里插入图片描述][672975efe4144640b699f9462bbd2b82.png]  
输入：graph = \[\[1,2\],\[3\],\[3\],\[\]\]  
输出：\[\[0,1,3\],\[0,2,3\]\]  
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

**示例 2：**  
![在这里插入图片描述][7462be20e26e41bc860e2f5684dab29d.png]  
输入：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）图的遍历  
思路参考[图论基础][Link 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();
        }
    }

[672975efe4144640b699f9462bbd2b82.png]: https://img-blog.csdnimg.cn/672975efe4144640b699f9462bbd2b82.png
[7462be20e26e41bc860e2f5684dab29d.png]: https://img-blog.csdnimg.cn/7462be20e26e41bc860e2f5684dab29d.png
[Link 1]: https://labuladong.github.io/algo/2/20/48/