0797. All Paths From Source to Target ======================================================================================================================== 题目信息 -------- :题号: 0797 :难度: Medium :主题: 有向无环图、路径枚举、邻接表 :原题: `LeetCode 0797 `_ :重点: 图保证是 DAG,起点固定为节点 0、终点固定为节点 ``n - 1``;需要返回所有有向路径,每条路径包含完整节点序列,结果顺序不限 题目重述 -------- 给定一个含 ``n`` 个节点的有向无环图,节点编号为 ``0`` 至 ``n - 1``。邻接表 ``graph[i]`` 列出所有可以从节点 ``i`` 通过一条有向边直接到达的节点。 请找出从节点 ``0`` 到节点 ``n - 1`` 的全部可能路径。每条路径用按经过顺序排列的节点编号数组表示,并且必须同时包含起点和终点。不同路径的返回顺序不限。 ``2 <= n <= 15``;邻接节点编号均合法,没有自环,同一邻接列表中的节点互不重复,输入保证不含有向环。 自建示例 -------- 路径可以经过不同数量的中间节点: .. code-block:: text 输入:graph = [[1,2,3],[4],[3,4],[4],[]] 输出:[[0,1,4],[0,2,3,4],[0,2,4],[0,3,4]] 解释:从 0 到 4 的有向路径恰好有四条,分别经由节点 1,经由节点 2、3,经由节点 2,以及直接经由节点 3;结果中的路径顺序可以不同。 起点无法到达终点: .. code-block:: text 输入:graph = [[],[]] 输出:[] 解释:图只有节点 0 和节点 1,且节点 0 没有任何出边。输入仍是合法 DAG,但不存在从起点到终点的路径,因此返回空数组。