首页创建无向图的邻接表表示，并求无向图（邻接表表示）中某个顶点的度

创建无向图的邻接表表示，并求无向图（邻接表表示）中某个顶点的度

时间: 2024-10-24 11:01:51 浏览: 121

无向图的邻接表是一种常用的图数据结构，它将每个顶点作为一节点，对应的值是一个列表，这个列表包含了与该顶点直接相连的所有其他顶点。对于每一对相连的顶点（u, v），在u的邻接列表中添加v，在v的邻接列表中也添加u。例如，如果有一个无向图，顶点集合为{A, B, C, D}，边集合为{(A, B), (B, C), (C, A), (D, A)}，那么它的邻接表表示可以是： - A: [B, D] - B: [A, C] - C: [A, B] - D: [A] 要计算某顶点的度，也就是其相邻顶点的数量，你只需要查看该顶点的邻接列表，长度即为其度。比如，顶点A的度就是其邻接列表[A: [B, D]]中有多少元素，这里是2。在Python中，你可以这样做： ```python def vertex_degree(vertex, adj_list): return len(adj_list[vertex]) # 使用上述邻接表 adj_list = { 'A': ['B', 'D'], 'B': ['A', 'C'], 'C': ['A', 'B'], 'D': ['A'] } degree_A = vertex_degree('A', adj_list) ```

阅读全文