广度优先搜索（Breadth-First Search）教程

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的宽度遍历树的每一层节点，直到找到目标节点或遍历完所有节点。

算法步骤

创建一个队列，用于存储待访问的节点。
将根节点加入队列。
当队列为空时，结束搜索。
从队列中取出一个节点，访问它。
将该节点的所有未访问的邻接节点加入队列。
重复步骤4和5，直到队列为空。

示例

假设有一个图如下：

    A
   / \
  B   C
 / \   \
D   E   F

使用广度优先搜索遍历该图，顺序为：A -> B -> C -> D -> E -> F

代码示例

以下是一个使用Python实现的广度优先搜索算法的示例：

from collections import deque

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 定义图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

# 执行广度优先搜索
bfs(graph, 'A')

扩展阅读

想要了解更多关于广度优先搜索的知识，可以阅读以下文章：