使用python进行dfs和bfs
时间: 2024-06-12 12:05:48 浏览: 13
以下是Python中的DFS和BFS实现示例:
深度优先搜索(DFS):
```python
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
```
广度优先搜索(BFS):
```python
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
```
在以上示例中,变量`graph`表示一个由节点及其相邻节点组成的字典。`start`参数表示搜索开始的节点。`visited`是一个集合,用于存储已访问过的节点。`stack`或`queue`是一个列表或队列,用于存储待访问的节点。`extend()`方法用于将待访问节点的相邻节点添加到`stack`或`queue`中。使用集合可以确保不会重复访问同一节点。