0797. 所有可能的路径【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

给你一个有 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. 🎯 s.1 - DFS

c

void dfs(int** graph, int* graphColSize, int n, int node, int* path, int pathLen, int*** res, int* resSize, int** resColSize) {
    if (node == n - 1) {
        (*res)[*resSize] = (int*)malloc(sizeof(int) * pathLen);
        memcpy((*res)[*resSize], path, sizeof(int) * pathLen);
        (*resColSize)[*resSize] = pathLen;
        (*resSize)++;
        return;
    }
    for (int i = 0; i < graphColSize[node]; i++) {
        path[pathLen] = graph[node][i];
        dfs(graph, graphColSize, n, graph[node][i], path, pathLen + 1, res, resSize, resColSize);
    }
}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
    int maxPaths = 1 << (graphSize - 1);
    int** res = (int**)malloc(sizeof(int*) * maxPaths);
    *returnColumnSizes = (int*)malloc(sizeof(int) * maxPaths);
    *returnSize = 0;
    int* path = (int*)malloc(sizeof(int) * graphSize);
    path[0] = 0;
    dfs(graph, graphColSize, graphSize, 0, path, 1, &res, returnSize, returnColumnSizes);
    free(path);
    return res;
}

js

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function (graph) {
  const res = []
  const n = graph.length
  const dfs = (node, path) => {
    if (node === n - 1) {
      res.push([...path])
      return
    }
    for (const next of graph[node]) {
      path.push(next)
      dfs(next, path)
      path.pop()
    }
  }
  dfs(0, [0])
  return res
}

py

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        n = len(graph)
        def dfs(node: int, path: list):
            if node == n - 1:
                res.append(path[:])
                return
            for nxt in graph[node]:
                path.append(nxt)
                dfs(nxt, path)
                path.pop()
        dfs(0, [0])
        return res

• 时间复杂度：$O(2^n\times n)$，路径数最多为 $2^{n-1}$，每条路径长度最多为 n
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• 由于是有向无环图，直接从节点 0 开始 DFS
• 到达节点 n-1 时记录当前路径，回溯探索所有可能的路径