试在邻接矩阵存储结构上实现图的基本操作InsertVex(G,v);InsertArc(G,v,w);DeleteVex(G,v);DeleteArc(G,v,w)
时间: 2023-03-20 15:01:24 浏览: 207
实验十二 图的基本操作—邻接矩阵存储结构.doc
邻接矩阵是一种常用的图的存储结构,其中每个顶点在矩阵的一行或一列中对应一个位置,如果顶点之间有边相连,则在相应的位置上存储边的信息(如权重);如果没有边相连,则相应的位置上存储一个特殊值(如0或无穷大)。
下面是在邻接矩阵存储结构上实现图的基本操作的示例代码:
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_matrix = [[0] * num_vertices for i in range(num_vertices)]
def insert_vex(self, v):
self.num_vertices += 1
# 在矩阵中添加一行和一列,初始值为0
for i in range(self.num_vertices-1):
self.adj_matrix[i].append(0)
self.adj_matrix.append([0]*self.num_vertices)
def insert_arc(self, v, w, weight=1):
# 在v行w列存储边的信息
self.adj_matrix[v][w] = weight
def delete_vex(self, v):
# 删除v行和v列
self.adj_matrix.pop(v)
for row in self.adj_matrix:
row.pop(v)
self.num_vertices -= 1
def delete_arc(self, v, w):
# 在v行w列清除边的信息
self.adj_matrix[v][w] = 0
```
在上面的代码中,`Graph`类包含了一个邻接矩阵和操作邻接矩阵的一些方法。构造函数`__init__`初始化矩阵,`insert_vex`方法插入一个新的顶点,`insert_arc`方法插入一条边,`delete_vex`方法删除一个顶点及其相关的边,`delete_arc`方法删除一条边。
注意,在实际的应用中,除了上述基本操作外,还有许多其他的操作和细节需要考虑。此外,对于大规模的图,邻接矩阵存储结构可能会消耗大量的内存,因此需要考虑其他的存储结构,如邻接表等。
阅读全文