首页pta 6-2 求采用邻接矩阵作为存储结构的无向图各顶点的度

pta 6-2 求采用邻接矩阵作为存储结构的无向图各顶点的度

时间: 2025-06-22 09:36:19 浏览: 14

### 计算无向图各顶点的度为了计算采用邻接矩阵作为存储结构的无向图中各个顶点的度数，可以按照如下方法实现：给定输入数据的第一行为图的顶点数目 \( n \) 和边的数量 \( m \)，随后的一行提供这 \( n \) 个顶点的名字（字符串形式），再之后的每一行则描述了一条连接两个节点之间的边。对于每一个顶点而言，在无向图里其度等于该顶点对应的行或列中的非零元素数量。由于这是针对无向图的情况讨论，因此只需要考虑一行即可得出相应顶点的度[^1]。下面是一个 Python 函数 `calculate_degrees` 的例子来完成这个任务: ```python def calculate_degrees(n, edges): # 初始化一个大小为n*n全为0的二维列表代表邻接矩阵 adjacency_matrix = [[0]*n for _ in range(n)] vertex_to_index = {vertex: idx for idx, vertex in enumerate(vertices)} # 基于提供的边填充邻接矩阵 for edge in edges: i, j = sorted([vertex_to_index[vertex] for vertex in edge]) adjacency_matrix[i][j] = 1 if i != j: # 防止自环被重复计数两次 adjacency_matrix[j][i] = 1 degrees = [] for row in adjacency_matrix: degree = sum(row) degrees.append(degree) return degrees if __name__ == "__main__": # 输入处理部分 n, m = map(int, input().split()) vertices = input().strip().split() edges = [input().strip().split() for _ in range(m)] result = calculate_degrees(n, edges) print(result) ``` 这段程序首先创建了一个基于输入构建起来的邻接矩阵，并通过遍历此矩阵来统计每个顶点相连的边数即为其度数。最后打印出所有顶点按顺序排列后的度数组成的结果列表。

阅读全文