假设图G采用邻接表存储,设计一个算法,判断顶点u到顶点v之间是否有路径,并对以下有向图G判断从顶点0到顶点5、从顶点0到顶点2是否有路径
时间: 2024-05-04 14:19:28 浏览: 183
可以使用深度优先搜索(DFS)来判断图中是否存在从顶点u到顶点v的路径。具体实现方法是从顶点u开始进行DFS遍历,如果遍历到顶点v,则说明存在路径;否则遍历结束仍未找到v,则说明不存在路径。
以下是使用邻接表存储的有向图G的示例代码:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def has_path(self, u, v):
visited = [False] * len(self.graph)
return self.dfs(u, v, visited)
def dfs(self, u, v, visited):
if u == v:
return True
visited[u] = True
for i in self.graph[u]:
if not visited[i]:
if self.dfs(i, v, visited):
return True
return False
# 以下是有向图G的邻接表表示
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
g.add_edge(4, 3)
g.add_edge(4, 5)
# 判断从顶点0到顶点5、从顶点0到顶点2是否有路径
print(g.has_path(0, 5)) # True
print(g.has_path(0, 2)) # True
```
通过DFS遍历可以判断从顶点0到顶点5、从顶点0到顶点2是否有路径,结果分别为True和True。
阅读全文