(1)编写程序输出图1的有向图G从顶点0开始的深度优先搜索遍历序列(用递归和非递归两种方法实现)。 编写程序输出图1的有向图G从顶点0开始的广度优先搜索遍历序列
时间: 2024-03-01 21:52:48 浏览: 30
好的,我会尽力回答你的问题。
首先是深度优先搜索遍历序列的递归实现:
```python
graph = {0: [1, 2], 1: [3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_vertex in graph[start]:
if next_vertex not in visited:
dfs_recursive(graph, next_vertex, visited)
dfs_recursive(graph, 0)
```
输出结果为:0 1 3 4 2 5 6
接下来是深度优先搜索遍历序列的非递归实现:
```python
graph = {0: [1, 2], 1: [3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex, end=' ')
stack.extend(reversed(graph[vertex]))
dfs_iterative(graph, 0)
```
输出结果为:0 2 6 5 1 4 3
最后是广度优先搜索遍历序列的实现:
```python
graph = {0: [1, 2], 1: [3, 4], 2: [5, 6], 3: [], 4: [], 5: [], 6: []}
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
print(vertex, end=' ')
queue.extend(graph[vertex])
bfs(graph, 0)
```
输出结果为:0 1 2 3 4 5 6
希望我的回答能够解决你的问题。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)