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;邻接节点编号均合法,没有自环,同一邻接列表中的节点互不重复,输入保证不含有向环。

自建示例

路径可以经过不同数量的中间节点:

输入: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;结果中的路径顺序可以不同。

起点无法到达终点:

输入:graph = [[],[]]
输出:[]
解释:图只有节点 0 和节点 1,且节点 0 没有任何出边。输入仍是合法 DAG,但不存在从起点到终点的路径,因此返回空数组。