完成代码,图的邻接矩阵和邻接表存储的实现
时间: 2024-12-15 15:20:49 浏览: 1
数据结构学习--图的邻接矩阵和邻接表存储
在计算机科学中,图是一种数据结构,用于表示顶点之间的连接关系。图的常见存储方式有邻接矩阵和邻接表。
**邻接矩阵**:
邻接矩阵是一个二维数组,其中行代表起点,列代表终点。如果两个顶点之间有边相连,则对应矩阵位置的值通常为1、true或者其他非零标识。例如,若有一个包含V个顶点的无向图,邻接矩阵就是VxV大小的数组:
```python
def create_adj_matrix(graph):
n = len(graph)
matrix = [[0] * n for _ in range(n)]
# 填充矩阵,假设graph[i]表示顶点i的邻居列表
for i, neighbors in enumerate(graph):
for neighbor in neighbors:
matrix[i][neighbor] = 1 # 无向图用1表示相邻,如果是有向图则可能需要其他标记
return matrix
```
**邻接表**:
邻接表则是使用链表来存储每个顶点的邻居信息。它将每个顶点映射到一个列表,列表中的元素是与其相邻的所有顶点。对于上述例子:
```python
def create_adj_list(graph):
adj_list = {v: [] for v in graph} # 初始化空字典,键是顶点,值是空列表
# 根据邻居列表填充邻接表
for i, neighbors in enumerate(graph):
for neighbor in neighbors:
adj_list[i].append(neighbor)
return adj_list
```
阅读全文