一个图G采用邻接矩阵作为存储结构,设计一个算法采用广度优先遍历判断顶点i到顶点j是否有路径(假设顶点i和j都是G中的顶点)的代码及主程序
时间: 2024-02-01 10:16:42 浏览: 51
图的存储与遍历(C语言实现)
5星 · 资源好评率100%
以下是基于邻接矩阵的广度优先遍历算法,用于判断顶点i到顶点j是否有路径:
```python
from queue import Queue
def bfs(graph, start, end):
visited = [False] * len(graph)
q = Queue()
q.put(start)
visited[start] = True
while not q.empty():
v = q.get()
if v == end:
return True
for i in range(len(graph)):
if graph[v][i] and not visited[i]:
q.put(i)
visited[i] = True
return False
```
其中,`graph`是邻接矩阵,`start`和`end`分别是起点和终点的下标。
以下是一个示例程序,用于测试上述算法:
```python
if __name__ == '__main__':
# 举例一个邻接矩阵
graph = [
[False, True, True, False],
[True, False, True, False],
[True, True, False, True],
[False, False, True, False]
]
i = 0
j = 3
if bfs(graph, i, j):
print(f"There is a path from vertex {i} to vertex {j}.")
else:
print(f"There is no path from vertex {i} to vertex {j}.")
```
输出结果为:
```
There is a path from vertex 0 to vertex 3.
```
阅读全文