所有可能的路径
题目链接
所有可能的路径
题目描述
注意点
- graph[i][j] != i（即不存在自环）
- graph[i] 中的所有元素 互不相同
- 保证输入为 有向无环图（DAG）
解答思路
- 深度优先遍历从节点0开始找到所能到达的节点，如果到达了节点n - 1，则记录路径
代码
class Solution {int n;public List<List<Integer>> allPathsSourceTarget(int[][] graph) {n = graph.length;List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();path.add(0);dfs(res, path, graph, 0);return res;}public void dfs(List<List<Integer>> res, List<Integer> path, int[][] graph, int point) {if (point == n - 1) {res.add(new ArrayList<>(path));}int[] nextPoints = graph[point];if (nextPoints.length == 0) {return;}for (int nextPoint : nextPoints) {path.add(nextPoint);dfs(res, path, graph, nextPoint);path.remove(path.size() - 1);}}
}
关键点
- 深度优先遍历的思想