试基于图的深度优先搜索策略写一算法,判别以邻接矩阵方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。实现。
时间: 2024-12-15 12:19:55 浏览: 12
C++实现图的邻接矩阵存储和广度、深度优先遍历实例分析
基于邻接矩阵的有向图深度优先搜索(DFS)遍历可以用来判断从顶点`i`是否可达顶点`j`。以下是一个简单的Python算法:
```python
def has_path(graph, vi, vj): # graph: 邻接矩阵表示的有向图,vi, vj: 起始和目标顶点
if vi == vj: # 如果起点等于终点,直接返回True
return True
visited = [False] * len(graph) # 记录已访问过的节点
stack = [vi] # 初始化栈,将起始点放入
while stack: # 当栈非空时,继续搜索
vertex = stack.pop() # 取出栈顶元素
if visited[vertex]: # 如果已经访问过这个节点,跳过
continue
visited[vertex] = True # 标记为已访问
for neighbor in range(len(graph[vertex])): # 遍历邻居
if not visited[neighbor] and graph[vertex][neighbor]: # 如果邻居未访问且有边相连
stack.append(neighbor) # 将邻居加入栈
if neighbor == vj: # 如果找到目标节点,返回True
return True
return False # 搜索结束后,如果没有到达vj,返回False,表示无路径
# 使用示例
graph = [
[0, 1, 1],
[0, 0, 1],
[0, 0, 0]
] # 这是一个有向图的邻接矩阵,其中vi=0, vj=2
has_path_to_vj = has_path(graph, 0, 2)
```
阅读全文