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

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

Принцип работы:

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

Характеристики:

• Полнота: Гарантирует нахождение решения, если оно существует.
• Оптимальность: Находит кратчайший путь в невесомом графе (где веса рёбер равны).
• Сложность по времени: Зависит от структуры графа, для E рёбер и V вершин — O(V + E).
• Сложность по памяти: O(V) в худшем случае, так как нужно хранить посещенные вершины и очередь.

Применение в QA:

• Поиск кратчайшего пути между узлами в тестовых сценариях.
• Исследование всех достижимых состояний системы при тестировании конечных автоматов.
• Тестирование доступности всех страниц веб-сайта при краулинге.

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

from collections import deque

# Пример представления дерева в виде словаря смежности
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

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

# Пример вызова
# bfs(graph, 'A')
# Вывод:
# A
# B
# C
# D
# E
# F