Алгоритм поиска в ширину (Breadth-First Search, BFS) — это метод обхода или поиска в графе или дереве, при котором сначала посещаются все вершины на текущем уровне, а затем переходят к вершинам следующего уровня.

Основные особенности:

Использует очередь для хранения вершин, которые нужно посетить.
Начинается с исходной вершины, добавляя её в очередь.
Пока очередь не пуста, извлекает вершину, посещает её соседей, которые ещё не были посещены, и добавляет их в очередь.

Пример применения: поиск кратчайшего пути в невзвешенном графе.

Пример на 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)

# Пример графа
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

Что такое алгоритм поиска в ширину?