O que é o algoritmo de busca em largura?

O algoritmo de busca em largura (BFS - Breadth-First Search) é um algoritmo de travessia ou busca numa árvore ou grafo. Começa pelo nó raiz (ou um nó arbitrário, se o grafo não for uma árvore) e explora todos os seus vizinhos imediatos, depois explora os vizinhos desses vizinhos, e assim por diante, nível por nível. BFS é implementado usando uma fila.

Princípio de funcionamento:

1. Colocar o nó inicial na fila.
2. Enquanto a fila não estiver vazia:
   • Remover um nó da fila.
   • Se o nó for o procurado, parar a busca.
   • Caso contrário, colocar na fila todos os seus vizinhos não visitados e marcá-los como visitados.

Características:

• Completude: Garante encontrar uma solução se ela existir.
• Óptimalidade: Encontra o caminho mais curto num grafo sem peso (onde os pesos das arestas são iguais).
• Complexidade em tempo: Depende da estrutura do grafo, para E arestas e V vértices — O(V + E).
• Complexidade em memória: O(V) no pior caso, pois é necessário armazenar os vértices visitados e a fila.

Aplicações em QA:

• Busca do caminho mais curto entre nós em cenários de teste.
• Exploração de todos os estados alcançáveis do sistema durante testes de autómatos finitos.
• Teste de acessibilidade de todas as páginas de um site durante crawling.

Exemplo (percorrendo uma árvore):

from collections import deque

# Exemplo de representação de árvore como dicionário de adjacência
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)

# Exemplo de chamada
# bfs(graph, 'A')
# Saída:
# A
# B
# C
# D
# E
# F