生成图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树的代码
时间: 2023-06-21 07:06:09 浏览: 55
以下是深度优先生成树的代码:
```python
def dfs(graph, vertex, visited, tree):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
tree[vertex].append(neighbor)
dfs(graph, neighbor, visited, tree)
def dfs_tree(graph, start):
visited = set()
tree = {v: [] for v in graph}
dfs(graph, start, visited, tree)
return tree
```
以下是广度优先生成树的代码:
```python
from collections import deque
def bfs_tree(graph, start):
visited = set()
tree = {v: [] for v in graph}
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
tree[vertex].append(neighbor)
queue.append(neighbor)
return tree
```
这两个函数都接受一个图和一个起始节点作为参数,并返回一个包含生成树的字典。生成树以字典的形式表示,其中键是节点,值是其子节点的列表。