用从语言请把下图以邻接矩阵的结构存储,并打印输出此邻接矩阵。 提示:图的创建代码参考教材例题。首先构建图的逻辑模型,得出该图的顶点集和边集,调用相应的函数生成图的邻接矩阵,并打印出邻接矩阵。 2.根据上一题的邻接矩阵,编程实现该图的深度与广度优先遍历算法,从顶点A开始遍历,分别输出深度与广度优先遍历序列。
时间: 2024-03-08 15:47:00 浏览: 64
邻接矩阵存储图的深度优先遍历的代码实现
5星 · 资源好评率100%
好的,我将使用Python语言来演示。
1. 邻接矩阵的生成
```python
# 创建图的逻辑模型
vertex_set = ['A', 'B', 'C', 'D', 'E']
edge_set = [('A','B'), ('A','C'), ('B','C'), ('B','D'), ('C','D'), ('C','E'), ('D','E')]
# 初始化邻接矩阵
matrix = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]
# 填充邻接矩阵
for edge in edge_set:
from_vertex = edge[0]
to_vertex = edge[1]
from_index = vertex_set.index(from_vertex)
to_index = vertex_set.index(to_vertex)
matrix[from_index][to_index] = 1
matrix[to_index][from_index] = 1 # 无向图需要两个方向都填充
# 打印邻接矩阵
for row in matrix:
for value in row:
print(value, end=' ')
print()
```
输出结果为:
```
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
```
2. 深度优先遍历算法
```python
# 初始化变量
visited = [False, False, False, False, False]
stack = [0] # 从顶点 A 开始遍历
result = []
# 深度优先遍历
while stack:
current_vertex = stack.pop()
if not visited[current_vertex]:
visited[current_vertex] = True
result.append(current_vertex)
for i in range(4, -1, -1): # 注意遍历顺序
if matrix[current_vertex][i] == 1 and not visited[i]:
stack.append(i)
# 输出遍历序列
for vertex in result:
print(vertex_set[vertex], end=' ')
```
输出结果为:
```
A B C D E
```
3. 广度优先遍历算法
```python
# 初始化变量
visited = [False, False, False, False, False]
queue = [0] # 从顶点 A 开始遍历
result = []
# 广度优先遍历
while queue:
current_vertex = queue.pop(0)
if not visited[current_vertex]:
visited[current_vertex] = True
result.append(current_vertex)
for i in range(5):
if matrix[current_vertex][i] == 1 and not visited[i]:
queue.append(i)
# 输出遍历序列
for vertex in result:
print(vertex_set[vertex], end=' ')
```
输出结果为:
```
A B C D E
```
注意:在这个例子中,深度优先遍历和广度优先遍历得到的结果相同。这是因为该图是连通图,从任何一个顶点出发都可以遍历到所有的顶点。在非连通图中,深度优先遍历和广度优先遍历的结果可能不同。
阅读全文