侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-30 / 0 评论 / 0 点赞 / 365 阅读 / 1,090 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

797. 所有可能的路径


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

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

示例 1:

image-20220530142836610

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2:

image-20220530142842557

输入: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;
    }
}
0

评论区