python实现宽度优先搜索

宽度优先搜索是一种广泛应用于树和图的算法，可以用于求解最短路径问题。下面是 Python 实现宽度优先搜索的代码：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

这个代码中，我们使用了 Python 内置的 `deque` 数据结构来实现队列。在 `bfs` 函数中，我们首先将起始节点加入队列，并将其标记为已访问。接着，我们使用 `while` 循环对队列进行遍历，取出队首元素，并打印该元素。随后，我们遍历该节点的所有邻居节点，将未访问的邻居节点加入队列，并将其标记为已访问。这样，我们就可以依次访问图中的所有节点。