广度优先搜索

[python]代码库

from collections import deque


def bfs(graph, start_node):
    # 使用队列存储待访问的节点
    queue = deque()
    # 使用集合记录已访问的节点
    visited = set()

    # 将起始节点加入队列和已访问集合
    queue.append(start_node)
    visited.add(start_node)

    while queue:
        # 从队列中取出一个节点
        node = queue.popleft()
        print(node)  # 输出节点

        # 遍历该节点的所有邻居节点
        for neighbor in graph[node]:
            # 若邻居节点未被访问，则加入队列和已访问集合
            if neighbor not in visited:
                queue.append(neighbor)
                print(neighbor)  # 输出节点

                visited.add(neighbor)


# 准备图的表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 调用bfs函数
start_node = 'A'
bfs(graph, start_node)