图的广度优先搜索 实现一个函数 `dfs`,接受一个有向图和起始节点作为参数,并返回从起始节点开始的深度优先搜索遍历结果。 要求使用递归方式实现深度优先搜索算法。
时间: 2024-02-06 09:09:04 浏览: 93
实现有向图的深度优先搜索算法
4星 · 用户满意度95%
抱歉,您提到的是广度优先搜索,而不是深度优先搜索。下面是广度优先搜索的实现,使用队列实现:
```python
from collections import deque
def bfs(graph, start):
visited = set() # 记录已经访问过的节点
queue = deque([start]) # 初始化队列,将起始节点加入队列
visited.add(start) # 将起始节点标记为已访问
result = [] # 记录遍历的结果
while queue: # 队列不为空
node = queue.popleft() # 取出队首节点
result.append(node) # 将节点加入遍历结果中
for neighbor in graph[node]: # 遍历当前节点的邻居节点
if neighbor not in visited: # 如果邻居节点没有被访问过
visited.add(neighbor) # 标记为已访问
queue.append(neighbor) # 将邻居节点加入队列
return result
```
其中,`graph` 表示有向图,使用字典表示。字典的键为节点,值为该节点的邻居节点列表。`start` 表示起始节点。函数返回从起始节点开始的广度优先搜索遍历结果。
阅读全文