【图, DFS, 递归, 栈】所有可能的路径

题目

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）

解题

方法一：DFS 栈

思路

使用一个栈(stack)辅助完成深搜，栈中存放一个路径，路径中最后一个节点是当前节点，把起始顶点到起始节点这个路径先入栈，当栈不为空时：

• 弹出栈顶路径(path)，获取当前顶点(curr)，如果当前顶点就是目标顶点的话，把当前路径加入答案中，继续下一次循环。
• 否则，遍历 curr 可以访问的所有节点的列表(graph[curr])。
• 新建一个新的路径(newPath)，在原路径的基础上加遍历到的节点(dest)，然后把这个新路径入栈。

代码

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> ans = new ArrayList<>();
        Deque<List<Integer>> stack = new LinkedList<>();
        stack.push(new ArrayList<>(){{ this.add(0); }});
        while (!stack.isEmpty()) {
            List<Integer> path = stack.pop();
            int curr = path.get(path.size() - 1);
            if (curr == n - 1) {
                ans.add(path);
                continue;
            }
            for (int dest : graph[curr]) {
                List<Integer> newPath = new ArrayList<>(){{ this.addAll(path); }};
                newPath.add(dest);
                stack.push(newPath);
            }
        }
        return ans;
    }
}

方法二：DFS 递归栈 回溯

思路

与方法一思路一致，不过使用递归(或称递归栈)代替上面的模拟栈完成深搜。
把路径(path)初始化，只放入起始顶点。传入起始顶点 0 开始递归：

• 传入的顶点即为当前递归到的顶点(curr)，如果当前顶点就是目标定点：
  新建一个路径集合深拷贝一份当前路径(path)，然后放入答案。
• 否则遍历当前顶点可以访问的所有顶点的数组(graph[curr])。
  把遍历到的每个顶点(dest)放入路径中，然后传入 dest 进行递归，完成递归后再把 dest 从路径中删除，以表示回溯。

代码

class Solution {
    private int[][] graph;
    private int n;
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>(){{ this.add(0); }};

    public List<List<Integer>> allPathsSourceTarget(int[][] _graph) {
        graph = _graph;
        n = graph.length;
        dfs(0);
        return ans;
    }

    private void dfs(int curr) {
        if (curr == n - 1) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int dest : graph[curr]) {
            path.add(dest);
            dfs(dest);
            path.remove(path.size() - 1);
        }
    }
}

方法三：BFS 队列

思路

使用一个队列(queue)辅助完成深搜，栈中存放一个路径，路径中最后一个节点是当前节点，把起始顶点到起始节点这个路径先入队，当队不为空时：

• 队头路径(path)出队，获取当前顶点(curr)，如果当前顶点就是目标顶点的话，把当前路径加入答案中，继续下一次循环。
• 否则，遍历 curr 可以访问的所有节点的列表(graph[curr])。
• 新建一个新的路径(newPath)，在原路径的基础上加遍历到的节点(dest)，然后把这个新路径入队。

代码

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> ans = new ArrayList<>();
        Deque<List<Integer>> queue = new LinkedList<>();
		queue.offer(new ArrayList<>(){{ this.add(0); }});
		while (!queue.isEmpty()) {
			List<Integer> path = queue.poll();
			int curr = path.get(path.size() - 1);
			if (curr == n - 1) {
				ans.add(new ArrayList<>(path));
				continue;
			}
            for (int dest : graph[curr]) {
                List<Integer> newPath = new ArrayList<>(){{ this.addAll(path); }};
                newPath.add(dest);
                queue.offer(newPath);
            }
		}
        return ans;
    }
}