已知有向图和无向图中的两个顶点,编写算法求有向图中所有简单路径
时间: 2024-05-15 14:12:12 浏览: 211
以下是一个深度优先搜索(DFS)算法的实现,用于在有向无环图(DAG)中找到所有简单路径。该算法基于递归,通过从给定的起点开始,向下递归访问所有可能的路径,直到到达目标点或无法继续下去为止。
```python
def find_all_paths(graph, start, end, path=[]):
"""
Find all paths from start to end in a directed acyclic graph (DAG)
"""
path = path + [start]
if start == end:
return [path]
if start not in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
new_paths = find_all_paths(graph, node, end, path)
for new_path in new_paths:
paths.append(new_path)
return paths
```
其中,`graph` 是一个字典,表示有向图的邻接表,`start` 和 `end` 分别是起点和终点的标识符,`path` 是当前路径的列表。该函数返回一个包含所有简单路径的列表。
示例用法:
```python
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['E'], 'D': ['E'], 'E': []}
start = 'A'
end = 'E'
print(find_all_paths(graph, start, end))
# Output: [['A', 'B', 'D', 'E'], ['A', 'B', 'E'], ['A', 'C', 'E']]
```
上述示例中,输入的有向图是以下形式:
```
A -> B -> D -> E
\-> C -> E
```
从起点 A 到终点 E 的所有简单路径分别是 A -> B -> D -> E、A -> B -> E 和 A -> C -> E。
阅读全文