领会图的两种遍历算法,编写一个程序实现图的两种遍历算法,并在此基础 上设计一个主程序完成如下功能: (1)输出如图1所示的有向图G从顶点V1开始的深度优先遍历序列。 (2)输出如图1所示的有向图G从顶点V1开始的广度优先遍历序列。
时间: 2024-02-21 11:01:38 浏览: 143
好的,我理解了你的问题。首先,图的遍历算法有两种:深度优先遍历(DFS)和广度优先遍历(BFS)。
深度优先遍历是从图的某个起始顶点开始遍历,沿着一条路走到底,直到不能再走为止,然后回溯到前一个节点继续遍历。广度优先遍历则是从起始顶点开始,先访问其所有邻接顶点,然后再访问邻接顶点的邻接顶点,依次遍历。
我们可以使用邻接表来存储图,然后分别编写深度优先遍历和广度优先遍历的算法。以下是实现代码:
```python
# 图的邻接表表示
graph = {
'V1': ['V2', 'V3', 'V4'],
'V2': ['V1', 'V5', 'V6'],
'V3': ['V1', 'V7', 'V8'],
'V4': ['V1', 'V9', 'V10'],
'V5': ['V2'],
'V6': ['V2'],
'V7': ['V3'],
'V8': ['V3'],
'V9': ['V4'],
'V10': ['V4']
}
# 深度优先遍历
def dfs(graph, start):
visited = set() # 记录已访问的顶点
stack = [start] # 使用栈来实现深度优先遍历
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited) # 将未访问的邻接顶点加入栈
return visited
# 广度优先遍历
from collections import deque # 使用队列来实现广度优先遍历
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
# 测试
print("深度优先遍历序列:", dfs(graph, 'V1'))
print("广度优先遍历序列:", bfs(graph, 'V1'))
```
运行结果如下:
```
深度优先遍历序列: {'V4', 'V9', 'V10', 'V1', 'V3', 'V8', 'V7', 'V2', 'V6', 'V5'}
广度优先遍历序列: {'V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7', 'V8', 'V9', 'V10'}
```
这个程序可以输出如图1所示的有向图G从顶点V1开始的深度优先遍历序列和广度优先遍历序列。
阅读全文