请给出bfs算法Python代码
时间: 2024-04-07 10:08:36 浏览: 11
以下是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`用于记录已访问过的节点,`queue`则是用于存储待访问的节点的队列。在每次循环中,从队列的左侧取出一个节点,如果该节点没有被访问过,则将其标记为已访问,并将其未访问过的邻居节点加入到队列中。最后返回已访问过的所有节点。
相关问题
bfs算法python
好的,以下是BFS算法的Python实现:
```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`是起始节点。
python bfs算法代码介绍
BFS(广度优先搜索)是一种图形搜索算法,它从根节点开始,逐层遍历整张图,直到找到目标节点或遍历完整张图。BFS 通常使用队列来实现。
以下是 Python 中 BFS 算法的代码实现:
```python
from collections import deque
def bfs(graph, start, end):
# 创建一个队列,用于存储要遍历的节点
queue = deque()
# 将起始节点加入队列
queue.append(start)
# 创建一个集合,用于存储已经遍历过的节点
visited = set()
# 遍历队列中的节点
while queue:
# 取出队列中的第一个节点
node = queue.popleft()
# 如果该节点已经被遍历过,则跳过
if node in visited:
continue
# 将该节点标记为已遍历
visited.add(node)
# 如果找到了目标节点,则返回 True
if node == end:
return True
# 将该节点的所有邻居加入队列
for neighbor in graph[node]:
queue.append(neighbor)
# 如果遍历完整张图都没有找到目标节点,则返回 False
return False
```
其中,`graph` 是一个字典,表示图的邻接表;`start` 和 `end` 分别表示起始节点和目标节点。