无向图如下所示: 1.建立无向图的邻接矩阵存储并输出。 2.建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。
时间: 2024-05-15 17:14:17 浏览: 132
对于给定的无向图,我们可以使用邻接矩阵和邻接表两种数据结构来存储和遍历。下面是实现这两种方法的代码:
```python
# 邻接矩阵存储方式
graph_matrix = [[0, 1, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 1, 0, 1, 1],
[0, 1, 1, 0, 1],
[0, 0, 1, 1, 0]]
# 输出邻接矩阵
print("邻接矩阵:")
for i in range(len(graph_matrix)):
for j in range(len(graph_matrix[i])):
print(graph_matrix[i][j], end=" ")
print()
# 邻接表存储方式
graph_list = [[1, 2], [0, 2, 3], [0, 1, 3, 4], [1, 2, 4], [2, 3]]
# 深度优先遍历
def dfs(graph, start, visited):
visited[start] = True
print(start, end=" ")
for i in graph[start]:
if not visited[i]:
dfs(graph, i, visited)
print("深度优先遍历:")
visited = [False] * len(graph_list)
dfs(graph_list, 0, visited)
print()
# 广度优先遍历
from collections import deque
def bfs(graph, start):
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for i in graph[vertex]:
if not visited[i]:
visited[i] = True
queue.append(i)
print("广度优先遍历:")
bfs(graph_list, 0)
```
输出结果为:
```
邻接矩阵:
0 1 1 0 0
1 0 1 1 0
1 1 0 1 1
0 1 1 0 1
0 0 1 1 0
深度优先遍历:
0 1 2 3 4
广度优先遍历:
0 1 2 3 4
```
以上代码中,邻接矩阵存储方式使用二维数组来表示图,其中 matrix[i][j] = 1 表示节点 i 和 j 之间有一条边,否则为 0。邻接表存储方式使用列表来表示图,其中 list[i] 表示与节点 i 相邻的节点列表。深度优先遍历使用递归方式实现,广度优先遍历使用队列实现。
阅读全文