所有可能的路径 Description 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节
时间: 2023-12-03 14:43:35 浏览: 39
点 graph[i][j] 有一条有向边)。例如,如果有一条有向边从节点 i 到节点 j,则 graph[i] 中会包含 j。
解题思路:
由于该图是有向无环图(DAG),所以我们可以使用深度优先搜索(DFS)来遍历所有可能的路径。从节点0开始,不断地往后搜索,直到搜索到节点n-1,就可以得到一条路径。为了避免重复遍历同一节点,我们需要使用一个visited数组来记录已经遍历过的节点。
具体实现可以参考下面的Python代码:
```python
def allPathsSourceTarget(graph):
n = len(graph)
res = []
visited = [False] * n
def dfs(node, path):
if node == n - 1:
res.append(path[:])
return
visited[node] = True
for nei in graph[node]:
if not visited[nei]:
path.append(nei)
dfs(nei, path)
path.pop()
visited[node] = False
dfs(0, [0])
return res
```
时间复杂度:O(2^n),其中n为节点数,因为每个节点都有两种状态:在路径中或不在路径中。
空间复杂度:O(n),需要一个visited数组和一个path数组来记录搜索过程中的状态。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)