LeetCode 题解工作台
所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG） ，请你找出从节点 0 到节点 n-1 的所有路径并输出（ 不要求按特定顺序 ） graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j] 存在一条有向边）。 示例 1： 输入： graph = [[1,…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个有 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.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i（即不存在自环）graph[i]中的所有元素 互不相同- 保证输入为 有向无环图（DAG）
解题思路
方法一
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
q = deque([[0]])
ans = []
while q:
path = q.popleft()
u = path[-1]
if u == n - 1:
ans.append(path)
continue
for v in graph[u]:
q.append(path + [v])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate understanding of graph traversal, especially DFS and backtracking.
- question_mark
Check if the candidate can handle path construction and backtracking efficiently.
- question_mark
Ensure the candidate explains edge cases, such as when no path exists or when the graph is fully connected.
常见陷阱
外企场景- error
Overcomplicating the solution with unnecessary algorithms like BFS when DFS is sufficient.
- error
Failing to handle the backtracking step correctly, leading to missing paths.
- error
Not managing memory effectively for larger graphs, which could cause stack overflow or excessive space usage.
进阶变体
外企场景- arrow_right_alt
Limit the number of nodes (n) to test edge cases and ensure efficient backtracking.
- arrow_right_alt
Modify the graph to add additional constraints, like limiting path lengths or adding weighted edges.
- arrow_right_alt
Implement a variant where paths must be ordered based on node labels.