试在邻接矩阵存储结构上实现图的基本操作
时间: 2023-03-20 13:01:22 浏览: 106
在邻接矩阵存储结构中,可以使用二维数组来表示图的节点之间的连接关系。假设我们有 $n$ 个节点,则邻接矩阵可以定义为一个 $n\times n$ 的矩阵 $A$,其中 $A_{i,j}=1$ 表示节点 $i$ 和节点 $j$ 之间存在一条边,而 $A_{i,j}=0$ 表示它们之间不存在边。
下面是在邻接矩阵存储结构上实现图的基本操作的代码示例:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.adj_matrix[v1][v2] = 1
self.adj_matrix[v2][v1] = 1
def remove_edge(self, v1, v2):
self.adj_matrix[v1][v2] = 0
self.adj_matrix[v2][v1] = 0
def is_adjacent(self, v1, v2):
return self.adj_matrix[v1][v2] == 1
def get_neighbors(self, v):
return [i for i in range(self.num_vertices) if self.adj_matrix[v][i] == 1]
```
在上面的代码中,`Graph` 类用于表示一个无向图,其中 `num_vertices` 属性表示节点的数量,而 `adj_matrix` 属性则表示邻接矩阵。`add_edge` 方法用于在节点 `v1` 和 `v2` 之间添加一条边,`remove_edge` 方法用于删除它们之间的边,`is_adjacent` 方法用于判断它们之间是否有边相连,`get_neighbors` 方法用于获取节点 `v` 的所有邻居节点。
注意,上述代码中的方法都是基于无向图的,如果要实现有向图,需要修改其中的方法以及邻接矩阵的定义。