创建无向图的邻接表表示,并求无向图中某个定点的度
时间: 2024-10-22 21:04:15 浏览: 59
基于邻接链表构建的有向图
5星 · 资源好评率100%
创建无向图的邻接表表示通常用于图算法中,它将每个顶点与其相邻的顶点列表关联起来。在邻接表数据结构中,图是由一个个链表组成,每个链表对应图中的一个顶点,链表中的元素是与该顶点相连的所有其他顶点。
例如,在邻接表形式下,如果顶点A有连接B、C两个顶点,顶点B有连接D、E两个顶点,那么存储结构会像这样:
```plaintext
A -> [B, C]
B -> [D, E]
C -> []
D -> []
E -> []
```
要计算无向图中某个定点的度(即与之相连的边的数量),你可以遍历与该顶点相关的链表,每遇到一个元素就加一。对于上述例子中的顶点A,它的度将是2,因为有两条从A出发的边。
以下是Python示例代码片段来获取指定顶点的度:
```python
def degree_of_vertex(vertex, adj_list):
return len(adj_list[vertex])
# 使用示例
adjacency_list = { 'A': ['B', 'C'], 'B': ['D', 'E'] } # 邻接表表示
degree_A = degree_of_vertex('A', adjacency_list) # 度为2
```
阅读全文