Šta je algoritam pretraživanja u širinu?

Алгоритам претраге у ширини (BFS - Breadth-First Search) је алгоритам обиласка или претраге у дрвету или графу. Он почиње од коренског чвора (или произвољног чвора ако граф није дрво) и истражује све његове непосредне суседе, затим суседе тих суседа и тако даље, ниво по ниво. BFS се реализује коришћењем реда.

Принцип рада:

1. Поставити почетни чвор у ред.
2. Док ред није празан:
   • Извући чвор из реда.
   • Ако је чвор тражени, зауставити претрагу.
   • У супротном, поставити у ред све његове непосећене суседе и означити их као посећене.

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

• Потпуност: Гарантује проналазак решења ако оно постоји.
• Оптималност: Налази најкраћи пут у графу без тежина (где су тежине ивица једнаке).
• Временска сложеност: Зависи од структуре графа, за E и 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