邻接表存储无向图函数题
时间: 2023-11-23 17:05:48 浏览: 95
好的,那我来给你讲解一下如何使用邻接表存储无向图并实现相关的函数。
首先,我们需要定义一个 `Graph` 类来表示无向图。它包含一个整数属性 `num_vertices` 表示图的顶点数,还有一个列表 `adj_list` 表示邻接表。我们可以使用 Python 的字典来实现这个列表,其中字典的键为顶点,值为该顶点对应的链表。
接下来,我们可以实现一些图的基本操作,例如添加顶点、添加边、获取顶点的邻居等等。下面是一个示例代码,你可以参考一下:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = {i: [] for i in range(num_vertices)}
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def get_neighbors(self, vertex):
return self.adj_list[vertex]
def __repr__(self):
return str(self.adj_list)
# 示例用法
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
print(g.get_neighbors(0)) # [1, 2]
print(g) # {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
```
在这个示例中,我们定义了一个 `Graph` 类,并实现了 `add_edge`、`get_neighbors` 和 `__repr__` 等方法。`add_edge` 方法用于添加边,该方法会同时修改两个顶点对应的链表;`get_neighbors` 方法可以返回某个顶点的邻居列表;`__repr__` 方法则用于打印邻接表。
你可以根据实际需要,自行扩展这个 `Graph` 类的功能。
阅读全文