【问题描述】 请基于邻接矩阵存储结构构建带权无向图,输出其深度遍历序列和广度遍历序列。 【输入形式】 输入数据有多行,首行m和n,表示图有m个顶点和n条边;第二行是m个顶点名称,中间空格分隔;之后为n条边,表示形式为:起点名称 终点名称 权值;最后一行为遍历的起点名称。 【输出形式】 输出数据有两行,首行为深度遍历序列,末行为广度遍历序列。 【样例输入】 4 5 A B C D A B 5 A C 2 A D 1 B C 4 C D 6 A 【样例输出】 A B C D A B C D
时间: 2024-02-04 12:02:09 浏览: 35
以下是Python的代码实现:
```python
from queue import Queue
# 邻接矩阵存储图
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * len(vertices) for _ in range(len(vertices))]
# 添加边
def add_edge(self, u, v, weight):
i = self.vertices.index(u)
j = self.vertices.index(v)
self.adj_matrix[i][j] = weight
self.adj_matrix[j][i] = weight # 无向图
# 深度优先搜索
def dfs(self, start):
visited = [False] * len(self.vertices)
dfs_result = []
def dfs_helper(vertex):
visited[self.vertices.index(vertex)] = True
dfs_result.append(vertex)
for i in range(len(self.vertices)):
if self.adj_matrix[self.vertices.index(vertex)][i] != 0 and visited[i] == False:
dfs_helper(self.vertices[i])
dfs_helper(start)
return dfs_result
# 广度优先搜索
def bfs(self, start):
visited = [False] * len(self.vertices)
bfs_result = []
q = Queue()
visited[self.vertices.index(start)] = True
q.put(start)
while not q.empty():
vertex = q.get()
bfs_result.append(vertex)
for i in range(len(self.vertices)):
if self.adj_matrix[self.vertices.index(vertex)][i] != 0 and visited[i] == False:
visited[i] = True
q.put(self.vertices[i])
return bfs_result
# 读入数据
m, n = map(int, input().split())
vertices = input().split()
graph = Graph(vertices)
for i in range(n):
u, v, weight = input().split()
graph.add_edge(u, v, int(weight))
start = input()
# 输出结果
dfs_result = graph.dfs(start)
bfs_result = graph.bfs(start)
print(' '.join(dfs_result))
print(' '.join(bfs_result))
```
输入样例:
```
4 5
A B C D
A B 5
A C 2
A D 1
B C 4
C D 6
A
```
输出样例:
```
A B C D
A B C D
```