请基于邻接矩阵存储结构构建带权无向图，输出其深度遍历序列和广度遍历序列。 【输入形式】 输入数据有多行，首行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

# 定义邻接矩阵存储结构
class MGraph:
    def __init__(self, vertices, edges):
        self.vertices = vertices
        self.edges = edges
        self.num_vertices = len(vertices)
        self.matrix = [[0] * self.num_vertices for i in range(self.num_vertices)]
        for edge in edges:
            start = vertices.index(edge[0])
            end = vertices.index(edge[1])
            weight = edge[2]
            self.matrix[start][end] = weight
            self.matrix[end][start] = weight

# 深度优先遍历
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor, weight in enumerate(graph.matrix[start]):
        if weight and neighbor not in visited:
            dfs(graph, neighbor, visited)

# 广度优先遍历
def bfs(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
    while queue:
        vertex = queue.pop(0)
        print(vertex, end=" ")
        for neighbor, weight in enumerate(graph.matrix[vertex]):
            if weight and neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 读入数据
m, n = map(int, input().split())
vertices = input().split()
edges = []
for i in range(n):
    start, end, weight = input().split()
    edges.append((start, end, int(weight)))
start_vertex = input()

# 构建图
graph = MGraph(vertices, edges)

# 深度优先遍历
dfs(graph, vertices.index(start_vertex))
print()

# 广度优先遍历
bfs(graph, vertices.index(start_vertex))
print()

输入：

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