1. 编写按键盘输入的数据建立图的邻接矩阵存储。 2. 编写图的深度优先遍历程序。 3. 编写图的广度优先遍历程序。 4. 设计一个选择菜单实现上述的各种基本操作 。
时间: 2024-01-24 20:16:49 浏览: 35
以下是 Python 代码实现:
```python
# 定义图类
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0 for _ in range(vertices)] for _ in range(vertices)]
# 添加边
def add_edge(self, v1, v2):
self.adj_matrix[v1][v2] = 1
self.adj_matrix[v2][v1] = 1
# 深度优先遍历
def dfs(self, start):
visited = [False] * self.vertices
self._dfs(start, visited)
def _dfs(self, vertex, visited):
visited[vertex] = True
print(vertex, end=' ')
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
self._dfs(i, visited)
# 广度优先遍历
def bfs(self, start):
visited = [False] * self.vertices
queue = [start]
visited[start] = True
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
# 打印邻接矩阵
def print_matrix(self):
for i in range(self.vertices):
for j in range(self.vertices):
print(self.adj_matrix[i][j], end=' ')
print()
# 主程序
def main():
vertices = int(input("请输入图的顶点数:"))
graph = Graph(vertices)
while True:
print("\n请选择操作:")
print("1. 添加边")
print("2. 深度优先遍历")
print("3. 广度优先遍历")
print("4. 打印邻接矩阵")
print("5. 退出")
choice = int(input("请输入选项:"))
if choice == 1:
v1 = int(input("请输入起点:"))
v2 = int(input("请输入终点:"))
graph.add_edge(v1, v2)
elif choice == 2:
start = int(input("请输入起始顶点:"))
print("深度优先遍历结果:", end='')
graph.dfs(start)
elif choice == 3:
start = int(input("请输入起始顶点:"))
print("广度优先遍历结果:", end='')
graph.bfs(start)
elif choice == 4:
print("邻接矩阵:")
graph.print_matrix()
elif choice == 5:
break
else:
print("输入有误,请重新选择!")
if __name__ == '__main__':
main()
```
使用方法:
1. 运行程序后,输入图的顶点数。
2. 选择要进行的操作,根据提示输入相应的参数。
3. 操作完成后,可以选择继续进行其他操作或退出程序。