0797. All Paths From Source to Target¶
题目信息¶
- 题号:
0797
- 难度:
Medium
- 主题:
有向无环图、路径枚举、邻接表
- 原题:
- 重点:
图保证是 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,但不存在从起点到终点的路径,因此返回空数组。