已知图以邻接矩阵作为存储结构,编写算法判断两个指定顶点之间是否存在路径。
时间: 2024-02-13 18:04:05 浏览: 19
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来判断两个指定顶点之间是否存在路径。
以下是使用DFS算法实现的伪代码:
```
// visited数组用于记录节点是否已经被访问过
// graph为邻接矩阵存储的图
// start为起始节点,end为目标节点
function dfs(start, end, visited, graph):
// 如果起始节点和目标节点相同,则直接返回true
if start == end:
return true
// 将起始节点标记为已访问
visited[start] = true
// 遍历起始节点的所有邻居节点
for i in range(len(graph[start])):
// 如果邻居节点未被访问过且与目标节点之间存在边,则递归搜索邻居节点
if not visited[i] and graph[start][i] != 0 and dfs(i, end, visited, graph):
return true
// 如果没有找到路径,则返回false
return false
```
可以通过调用该函数来判断两个指定顶点之间是否存在路径,如下所示:
```
visited = [false] * len(graph)
start = 0
end = 5
if dfs(start, end, visited, graph):
print("存在路径")
else:
print("不存在路径")
```
如果存在路径,则输出“存在路径”,否则输出“不存在路径”。