已知图以邻接矩阵作为存储结构,请编写算法代码判断两个指定顶点之间是否存在路径。
时间: 2024-03-23 08:38:24 浏览: 28
好的,以下是使用深度优先搜索(DFS)算法来判断两个指定顶点之间是否存在路径的算法代码实现:
```python
def dfs(graph, visited, start, end):
"""
:param graph: 图的邻接矩阵表示
:param visited: 记录节点是否已经被访问的数组
:param start: 起始节点
:param end: 终止节点
:return: 如果存在一条从start到end的路径则返回True,否则返回False
"""
visited[start] = True # 标记已经访问过起始节点
if start == end: # 如果找到终止节点,返回True
return True
for i in range(len(graph[start])): # 遍历与起始节点相邻的节点
if graph[start][i] == 1 and not visited[i]: # 如果找到未访问过的相邻节点
if dfs(graph, visited, i, end): # 递归查找从相邻节点到终止节点的路径
return True
return False # 如果无法找到从起始节点到终止节点的路径,则返回False
# 示例代码:
graph = [[0, 1, 0, 0, 1],
[1, 0, 1, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 0, 0, 1, 0]]
visited = [False] * len(graph)
start = 0
end = 3
if dfs(graph, visited, start, end):
print(f"There exists a path from vertex {start} to vertex {end}.")
else:
print(f"There is no path from vertex {start} to vertex {end}.")
```
其中,graph表示邻接矩阵,visited为记录节点是否已经被访问的数组,start为起始节点的下标,end为终止节点的下标。在算法中,我们首先标记起始节点已经被访问过,然后遍历与起始节点相邻的节点,如果相邻节点未被访问过,则递归查找从相邻节点到终止节点的路径。如果找到终止节点,则返回True,否则继续查找。如果无法找到从起始节点到终止节点的路径,则返回False。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)