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

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

Основные принципы:

1. Использует очередь (Queue): Для хранения узлов, которые нужно посетить.
2. Посещает по уровням: Обходит узлы по уровням, шаг за шагом удаляя узлы из начала очереди и добавляя их непосещенных смежных узлов в конец очереди.
3. Гарантирует нахождение кратчайшего пути: В невзвешенном графе BFS гарантирует нахождение кратчайшего пути от начального узла до любого другого достижимого узла.

Этапы выполнения:

1. Добавить начальный узел в очередь. Пометить его как посещенный.
2. Пока очередь не пуста:
   • Извлечь узел из начала очереди.
   • Для каждого непосещенного смежного узла извлеченного узла:
     • Добавить его в конец очереди.
     • Пометить его как посещенный.

Пример (обход графа):

Пусть у нас есть граф: A -> B, A -> C, B -> D, C -> E

Очередь: [] Посещенные: {}

1. Добавляем A в очередь. Помечаем A как посещенное. Очередь: [A] Посещенные: {A}
2. Очередь не пуста. Извлекаем A. Соседи A: B, C. B не посещен, C не посещен. Добавляем B в очередь, помечаем B. Добавляем C в очередь, помечаем C. Очередь: [B, C] Посещенные: {A, B, C}
3. Очередь не пуста. Извлекаем B. Соседи B: D. D не посещен. Добавляем D в очередь, помечаем D. Очередь: [C, D] Посещенные: {A, B, C, D}
4. Очередь не пуста. Извлекаем C. Соседи C: E. E не посещен. Добавляем E в очередь, помечаем E. Очередь: [D, E] Посещенные: {A, B, C, D, E}
5. Очередь не пуста. Извлекаем D. Соседи D: нет непосещенных. Очередь: [E] Посещенные: {A, B, C, D, E}
6. Очередь не пуста. Извлекаем E. Соседи E: нет непосещенных. Очередь: [] Посещенные: {A, B, C, D, E}
7. Очередь пуста. Обход завершен.

Порядок обхода: A, B, C, D, E.

Применяется для:

• Поиска кратчайшего пути в невзвешенном графе.
• Нахождения всех достижимых узлов.
• Проверки связности графа.
• В алгоритмах сетевого маршрутирования.

# Пример реализации BFS на Python
import collections

def bfs(graph, start_node):
    visited = set()  # Множество посещенных узлов
    queue = collections.deque([start_node]) # Очередь для обхода

    visited.add(start_node) # Помечаем стартовый узел как посещенный

    while queue:
        current_node = queue.popleft() # Извлекаем узел из начала очереди
        print(current_node)  # Обрабатываем узел (например, печатаем)

        # Добавляем в очередь непосещенных соседей текущего узла
        if current_node in graph: # Проверка на наличие соседей
            for neighbor in graph[current_node]:
                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 с узла 'A'
# bfs(graph, 'A')