python广度优先搜索算法实验

在Python中，宽度优先搜索（Breadth-First Search, BFS）是一种常用的图遍历算法，它按照层级顺序逐层探索节点。实验通常涉及到创建一个图数据结构（如邻接矩阵或邻接表），然后从给定的起始节点开始，按顺序访问其所有相邻节点，再递归地对每个未访问过的邻居进行相同的操作。

以下是简单的BFS算法步骤：

1. 创建一个队列，并将起点加入队列。
2. 初始化一个集合或字典来记录已经访问过的节点，防止重复访问。
3. 当队列非空时，循环执行以下操作：
a. 弹出队首节点。
b. 将该节点标记为已访问。
c. 遍历该节点的所有邻接节点，如果它们不在已访问集合中，则将它们加入队列，并添加到已访问集合中。
4. 继续这个过程直到队列为空，所有可达的节点都被访问过。

以下是一个使用Python的简单BFS示例，假设我们有一个无向图表示为邻接列表：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()  # Dequeue the first node
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Visit the vertex
            queue.extend(graph[vertex] - visited)  # Enqueue unvisited neighbors

# 示例：
# graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] }
bfs(graph, 'A')  # 这将按照BFS顺序打印节点