LeetCode第797题: 所有可能的路径

1.问题描述

2.问题分析

1.问题描述

给你一个有 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）

2.问题分析

思路分析：有向无环图（Directed acyclic graph, DAG）是图论中的一个概念，它指的是一个无回路的有向图。问题是要找到0节点到n − 1节点的所有路径，对于所有路径的问题，我们可以用深度优先搜索来做（广度优先搜索也可以）。

这题让在有向无环图中输出从顶点0到顶点n-1的所有路径，可以使用dfs，从顶点0开始搜索，搜索所有路径，因为是无环的，所以搜索的时候不会出现死循环。到顶点n-1的时候就把这条路径上所有的点都保存下来。因为是dfs搜索，往下走的时候选择节点，往回走的时候要记得撤销选择。

JAVA

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> ans = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    path.add(0);// 把起始节点0加进来
    dfs(graph, 0, ans, path);
    return ans;
}

private void dfs(int[][] graph, int index, List<List<Integer>> ans, List<Integer> path) {
    //  到最后一个节点的时候，说明找了一个一条有效路径
    if (index == graph.length - 1) {
        ans.add(new ArrayList<>(path));
        return;
    }
    // 当前节点指向哪些节点（可以看做是n叉树的子节点，然后遍历他的子节点）
    int[] directs = graph[index];
    for (int i = 0; i < directs.length; i++) {
        path.add(directs[i]);// 把当前节点加入到路径中
        dfs(graph, directs[i], ans, path);// 递归
        path.remove(path.size() - 1); // 撤销选择
    }
}

C++

public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        vector<vector<int>> ans;
        vector<int> path;
        path.push_back(0);// 把起始节点0加进来
        dfs(graph, 0, ans, path);
        return ans;
    }

    void dfs(vector<vector<int>> &graph, int index, vector<vector<int>> &ans, vector<int> &path) {
        //  到最后一个节点的时候，说明找了一个一条有效路径
        if (index == graph.size() - 1) {
            ans.emplace_back(path);
            return;
        }
        // 当前节点指向哪些节点（可以看做是n叉树的子节点，然后遍历他的子节点）
        for (int g: graph[index]) {
            path.emplace_back(g);// 把当前节点加入到路径中
            dfs(graph, g, ans, path);// 递归
            path.pop_back(); // 撤销选择
        }
    }

void dfs(int **graph, int graphSize, int *graphColSize, int *returnSize,
         int **returnColumnSizes, int **ans, int *path, int v, int count) {
    //  到最后一个节点的时候，说明找了一个一条有效路径
    if (v == graphSize - 1) {
        ans[*returnSize] = malloc(count * sizeof(int));
        memcpy(ans[*returnSize], path, count * sizeof(int));
        (*returnColumnSizes)[(*returnSize)++] = count;
        return;
    }
    // 当前节点指向哪些节点（可以看做是n叉树的子节点，然后遍历他的子节点）
    for (int i = 0; i < graphColSize[v]; ++i) {
        path[count++] = graph[v][i];// 把当前节点加入到路径中
        dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, graph[v][i], count);// 递归
        count--;// 撤销选择
    }
}

int **allPathsSourceTarget(int **graph, int graphSize, int *graphColSize, int *returnSize, int **returnColumnSizes) {
    int **ans = malloc(20000 * sizeof(int *));
    int *path = malloc(15 * sizeof(int));
    int v = 0;
    int count = 0;
    *returnSize = 0;
    *returnColumnSizes = malloc(20000 * sizeof(int));
    path[count++] = v;// 把起始节点0加进来
    dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, v, count);
    return ans;
}

Python

def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
    def dfs(index):
        # 到最后一个节点的时候，说明找了一个一条有效路径
        if index == len(graph) - 1:
            ans.append(path[:])
            return
        # 当前节点指向哪些节点（可以看做是n叉树的子节点，然后遍历他的子节点）
        for direct in graph[index]:
            path.append(direct)  # 把当前节点加入到路径中
            dfs(direct)  # 递归
            path.pop()  # 撤销选择

    ans = []
    path = [0]
    dfs(0)
    return ans

复杂度分析