邻接矩阵实现图的构造 (包含有向图和无向图) 实现 插入或者删除 顶点、边的完整运行代码
时间: 2024-03-24 09:40:36 浏览: 19
好的,下面是邻接矩阵实现有向图和无向图的构造、插入或删除顶点和边的完整运行代码:
```python
class Graph:
def __init__(self, vertices, directed=False):
self.vertices = vertices
self.directed = directed
self.adj_matrix = [[0] * vertices for i in range(vertices)]
def insert_vertex(self):
self.vertices += 1
for i in range(self.vertices - 1):
self.adj_matrix[i].append(0)
self.adj_matrix.append([0] * self.vertices)
def delete_vertex(self, vertex):
for i in range(self.vertices):
del self.adj_matrix[i][vertex]
del self.adj_matrix[vertex]
self.vertices -= 1
def insert_edge(self, vertex1, vertex2, weight=1):
self.adj_matrix[vertex1][vertex2] = weight
if not self.directed:
self.adj_matrix[vertex2][vertex1] = weight
def delete_edge(self, vertex1, vertex2):
self.adj_matrix[vertex1][vertex2] = 0
if not self.directed:
self.adj_matrix[vertex2][vertex1] = 0
def print_graph(self):
for row in self.adj_matrix:
print(row)
# 测试无向图的构造、插入或删除顶点和边
graph = Graph(3)
graph.insert_edge(0, 1)
graph.insert_edge(1, 2)
graph.insert_vertex()
graph.insert_edge(2, 3)
graph.delete_edge(1, 2)
graph.delete_vertex(3)
graph.print_graph()
# 测试有向图的构造、插入或删除顶点和边
graph = Graph(3, True)
graph.insert_edge(0, 1)
graph.insert_edge(1, 2)
graph.insert_vertex()
graph.insert_edge(2, 3)
graph.delete_edge(1, 2)
graph.delete_vertex(3)
graph.print_graph()
```
在这个示例代码中,我们定义了一个Graph类,用于实现有向图和无向图的构造、插入或删除顶点和边。在初始化函数中,我们除了定义邻接矩阵adj_matrix,还定义了一个directed变量,用于表示图是否为有向图。在插入顶点和边、删除顶点和边时,我们只需要对邻接矩阵进行相应的修改即可。最后,我们可以通过print_graph方法打印出邻接矩阵来验证我们的操作是否正确。
在测试代码中,我们先测试了一个无向图的构造、插入或删除顶点和边的过程,然后测试了一个有向图的构造、插入或删除顶点和边的过程。你可以自己调整代码中的参数,来测试不同的图的构造和操作。