建立图的邻接表存储结构,并将邻接表输出代码实现
时间: 2023-11-05 08:11:59 浏览: 109
以邻接表的形式建立和存储图
5星 · 资源好评率100%
好的,以下是图的邻接表存储结构的代码实现:
```python
class Graph:
def __init__(self, n):
self.n = n
self.adj_list = [[] for _ in range(n)]
def add_edge(self, u, v):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def print_adj_list(self):
for i in range(self.n):
print(f"{i}: ", end="")
for j in self.adj_list[i]:
print(j, end=" ")
print()
```
其中,`Graph` 类接受一个参数 `n` 表示图的节点数,构建一个长度为 `n` 的列表,每个元素都是一个空列表,表示该节点的邻接表。`add_edge()` 方法用于向图中添加一条边,将边所连接的两个节点加入对应的邻接表中。`print_adj_list()` 方法用于输出邻接表。
使用时,可以先构建一个 `Graph` 对象,然后向其中添加边,并输出邻接表。例如:
```python
# 构建一个节点数为 5 的图
g = Graph(5)
# 添加边
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
# 输出邻接表
g.print_adj_list()
```
输出结果为:
```
0: 1 2
1: 0 2
2: 0 1 3
3: 2 4
4: 3
```
其中,第 i 个元素表示节点 i 的邻接表,列表中的元素表示与节点 i 相邻的节点。由于无向图的邻接表是有向的,因此在添加边时需要将两个节点都加入对方的邻接表中。
阅读全文