现在有n个城市,城市之间有坐火车达到,但是城市之间的铁路是有方向 的,即:[1,2]表示只可以 从1到达2, 给定以下城市间的铁路路线设计,请求出给定城市0到城市(n-1)之间的所有路径 示例1: 输入:[[O,1],[0,2],[1,3], [2,3]] 输出:[0,1,3],[0,2,3] 示例2: 输入:[[0,1],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[3,4]] 输出:[[O,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]] 提交代码要求以上的两个示例测试通过,需要有测试代码
时间: 2023-08-18 13:26:57 浏览: 47
以下是Python代码实现,包括了路径搜索函数和两个测试用例的验证:
```python
from typing import List
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
def dfs(node, path):
if node == len(graph) - 1:
res.append(path)
return
for nei in graph[node]:
dfs(nei, path + [nei])
res = []
dfs(0, [0])
return res
# 测试用例1
graph1 = [[0,1],[0,2],[1,3],[2,3]]
print(allPathsSourceTarget(graph1)) # [[0, 1, 3], [0, 2, 3]]
# 测试用例2
graph2 = [[0,1],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[3,4]]
print(allPathsSourceTarget(graph2)) # [[0, 4], [0, 3, 4], [0, 1, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4]]
```
解释一下代码实现:
我们定义一个深度优先搜索的函数 `dfs(node, path)`,其中 `node` 表示当前节点,`path` 表示当前路径。如果当前节点是目标节点 `len(graph)-1`,则将当前路径加入结果列表 `res`。否则,遍历当前节点的所有邻居节点(即可以到达的节点),并将邻居节点加入路径中,递归调用 `dfs(nei, path + [nei])`。在主函数中,我们从起始节点0开始调用 `dfs(0, [0])`,并返回结果列表 `res`。