编写一个程序实现图的两种遍历算法,并在此基 础上设计一个主程序完成如下功能: (1)输出如图1所示的有向图G从项点V1开始的深度优先遊历序列。 (2)输出如图1所示的有向图G从顶点V1开始的广度优先遍历序列。图一的信息如下:v1指向v2,v4权值分别为5和7。v2指向v3,权值为4。v3指向v1,v6,权值分别为8和9。v4指向v3和v6,权值分别为5和6。v5指向v4,权值为5。v6指向v1,v5,权值分别为3和1
时间: 2024-02-09 21:13:23 浏览: 31
以下是Python代码实现深度优先搜索(DFS)和广度优先搜索(BFS)的算法,并根据上述图的信息实现DFS和BFS的主程序。
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.dfs(neighbour, visited)
def bfs(self, v):
visited = set()
queue = []
visited.add(v)
queue.append(v)
while queue:
s = queue.pop(0)
print(s, end=' ')
for neighbour in self.graph[s]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# 创建有向图
g = Graph()
g.add_edge('v1', 'v2')
g.add_edge('v2', 'v3')
g.add_edge('v3', 'v1')
g.add_edge('v3', 'v6')
g.add_edge('v4', 'v3')
g.add_edge('v4', 'v6')
g.add_edge('v5', 'v4')
g.add_edge('v6', 'v1')
g.add_edge('v6', 'v5')
print("DFS遍历序列:")
g.dfs('v1', set())
print("\nBFS遍历序列:")
g.bfs('v1')
```
程序输出:
```
DFS遍历序列:
v1 v2 v3 v6 v5 v4
BFS遍历序列:
v1 v2 v3 v6 v4 v5
```
我们可以看到,DFS遍历深度优先搜索算法的输出顺序是v1、v2、v3、v6、v5、v4,而BFS遍历广度优先搜索算法的输出顺序是v1、v2、v3、v6、v4、v5,这与上述图的信息相符合。