Какво е алгоритъмът за търсене в ширина?

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

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

1. Поставете началния възел в опашката.
2. Докато опашката не е празна:
   • Извадете възел от опашката.
   • Ако възелът е търсеният, спирайте търсенето.
   • В противен случай, поставете всички негови непосетени съседи в опашката и ги маркирайте като посетени.

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

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

Приложения в QA:

• Търсене на най-краткия път между възлите в тестови сценарии.
• Изследване на всички достижими състояния на системата при тестване на крайни автомати.
• Тестиране на достъпността на всички страници на уебсайт при crawling.

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

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