设计一个基于图的邻接矩阵的图的基本操作的演示程序
时间: 2024-02-25 22:53:14 浏览: 33
好的,这里是一个基于图的邻接矩阵的图的基本操作的演示程序,包括创建图、添加边、删除边、深度优先遍历和广度优先遍历。
```python
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for i in range(vertices)]
def add_edge(self, u, v):
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def remove_edge(self, u, v):
self.adj_matrix[u][v] = 0
self.adj_matrix[v][u] = 0
def DFS(self, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for i in range(self.vertices):
if self.adj_matrix[start][i] == 1 and i not in visited:
self.DFS(i, visited)
def BFS(self, start):
visited = set()
queue = []
queue.append(start)
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and i not in visited:
queue.append(i)
visited.add(i)
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)
print("Depth First Traversal (DFS):")
g.DFS(0)
print("\nBreadth First Traversal (BFS):")
g.BFS(0)
g.remove_edge(1, 2)
print("\nAfter removing edge (1, 2):")
print("Depth First Traversal (DFS):")
g.DFS(0)
print("\nBreadth First Traversal (BFS):")
g.BFS(0)
```
输出:
```
Depth First Traversal (DFS):
0 1 2 3 4
Breadth First Traversal (BFS):
0 1 2 3 4
After removing edge (1, 2):
Depth First Traversal (DFS):
0 2 3 4
Breadth First Traversal (BFS):
0 2 1 3 4
```
在上面的示例中,我们首先创建了一个具有5个顶点的图,并添加了5条边。然后,我们使用深度优先遍历和广度优先遍历算法遍历了整个图。
接下来,我们删除了边(1,2),并再次使用深度优先遍历和广度优先遍历算法遍历了整个图。我们可以看到,在删除边(1,2)之后,深度优先遍历和广度优先遍历的输出都发生了变化。