dfs和bfs python
时间: 2023-05-26 17:04:51 浏览: 144
基于python模拟bfs和dfs代码实例
深度优先搜索(DFS)和广度优先搜索(BFS)是常用的图搜索算法,它们可以应用于迷宫、排列组合、树结构等问题。下面是Python实现DFS和BFS的样例代码:
DFS:
```python
def dfs(graph, start, visited=set()):
visited.add(start)
for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
return visited
```
BFS:
```python
def bfs(graph, start):
visited, queue = set(), [start]
visited.add(start)
while queue:
node = queue.pop(0)
for next_node in graph[node] - visited:
visited.add(next_node)
queue.append(next_node)
return visited
```
其中,graph表示图结构,start表示起点节点。在DFS中,visited用于记录已访问的节点。在BFS中,queue用于记录待访问节点。
阅读全文