📃 题目描述

题目链接：

• 剑指 Offer II 110. 所有路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 797. 所有可能的路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。

graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。

示例 1：

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

🔔 解题思路

搜索一个节点到另一个节点的所有路径，BFS 和 DFS 都可以，不过 DFS 效率更高

深度优先搜索通常用递归实现。

• 从节点 0 出发开始搜索
• 每当搜索到节点 i 时，先将该节点添加到路径中去
  • 如果该节点正好是节点 n-1，那么就找到了一条从节点 0 到节点 n-1 的路径
  • 如果不是，则从 graph[i] 找到每个相邻的节点并用同样的方法进行搜索
• 当从节点 i 出发能够抵达的所有节点都搜索完毕之后，将回到前一个节点搜索其他与之相邻的节点。在回到前一个节点之前，需要将节点 i 从路径中删除。

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        
        // 起点加入 p
        path.add(0);
        dfs(0, graph, res, path);
        
        return res;
    }
	
    // dfs 从 source 到 n - 1 的路径
    private void dfs(int source, int[][] graph, List<List<Integer>> res, List<Integer> path) {
        if (source == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }
        
        // 从 source 到 n - 1 的路径 = 从 source 到 neighboor + 从 neighboor 到 n - 1 的路径
        for (int neighbor : graph[source]) {
            path.add(neighbor);
            dfs(neighbor, graph, res, path);
            path.remove(path.size() - 1);
        }
    }
}

可以发现，上述代码中没有判断一个节点是否已经访问过。在做图搜索的时候通常需要判断一个节点是否已经访问过，这样可以避免反复访问环中的节点。由于这个题目已经明确图是一个有向无环图，因此没有必要担心重复访问环中的节点。

另外，可能有的读者觉得上述代码和实现回溯法的代码很相像，这是因为回溯法从本质上来说就是深度优先搜索。

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：