1.从键盘输入无向图若干个顶点信息，以！作为结束； 2.输入一组顶点信息，分别表示图中边依附的两个顶点和权值，以-1 作为输入结束；以邻接矩阵作为存储； 3.输入起始顶点 4.利用prim算法求解最小生成树，输出每一步选出的边； 5.输出最小生成树的代价。 【输入样例】 ABCDEF! 0 1 9 0 2 10 1 2 7 1 3 5 2 4 6 2 5 7 3 4 11 4 5 8 -1 C 【输出样例】 CE 6 CB 7 BD 5 CF 7 BA 9 34

以下是基于邻接矩阵的 Prim 算法实现的 Python 代码：

import sys

# 读入顶点信息
vertices = input().strip().split('!')[0]
n = len(vertices)

# 读入边信息
adj_matrix = [[0] * n for _ in range(n)]
while True:
    line = input().strip()
    if line == '-1':
        break
    v1, v2, weight = map(int, line.split())
    adj_matrix[v1][v2] = weight
    adj_matrix[v2][v1] = weight

# 读入起始顶点
start_vertex = input().strip()

# 初始化 Prim 算法
visited = set(start_vertex)
min_cost = [sys.maxsize] * n
min_cost[ord(start_vertex) - ord('A')] = 0

# 执行 Prim 算法
while len(visited) < n:
    min_edge = (None, None, sys.maxsize)
    for v in visited:
        for i in range(n):
            if i == ord(v) - ord('A') or chr(i + ord('A')) in visited:
                continue
            if adj_matrix[ord(v) - ord('A')][i] < min_cost[i]:
                min_cost[i] = adj_matrix[ord(v) - ord('A')][i]
            if adj_matrix[ord(v) - ord('A')][i] < min_edge[2]:
                min_edge = (v, chr(i + ord('A')), adj_matrix[ord(v) - ord('A')][i])
    print(min_edge[0] + min_edge[1], min_edge[2])
    visited.add(min_edge[1])

# 计算最小生成树代价
cost = sum(min_cost)
print(cost)

输入样例：

ABCDEF!
0 1 9
0 2 10
1 2 7
1 3 5
2 4 6
2 5 7
3 4 11
4 5 8
-1
C

输出样例：

CE 6
CB 7
BD 5
CF 7
BA 9
34