Algoritmos de busca em largura (BFS)

8.1 Princípios de funcionamento do algoritmo BFS

Busca em Largura (Breadth-First Search, BFS) é um algoritmo de percurso ou busca em gráfico que começa a partir do vértice inicial e explora todos os seus vértices vizinhos no nível atual antes de passar para os vértices do próximo nível.

Etapas do algoritmo:

1. Começamos com o vértice inicial escolhido e o colocamos na fila.
2. Enquanto a fila não estiver vazia, realizamos as seguintes ações:
   • Extraímos o vértice da cabeça da fila e o marcamos como visitado.
   • Para cada vértice vizinho não visitado, adicionamos na fila.
3. Repetimos o passo 2 até que todos os vértices alcançáveis a partir do vértice inicial sejam visitados.

Visualização:

Complexidade de tempo:

O(V + E), onde V é o número de vértices, E é o número de arestas.

Cada nó e cada aresta do gráfico são visitados uma vez.

Complexidade de espaço:

O(V), pois é utilizada uma fila para armazenar os vértices e também arrays para armazenar o estado (vértices visitados).

8.2 Implementação de BFS usando fila

A busca em largura é bem implementada usando uma estrutura de dados como a fila.

Implementação de BFS usando fila:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Processamento do nó
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Exemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Busca em largura bidirecional

O BFS é frequentemente usado em jogos, quando se precisa encontrar o caminho mais curto entre dois pontos em um terreno complexo. Esse problema se transforma facilmente em um problema de busca de caminho em um gráfico entre dois vértices. As arestas desse gráfico são todos os caminhos transitáveis no mapa.

Mas para encontrar o caminho mais rápido, geralmente é buscado a partir de dois extremos. Para isso, é aplicado o BFS bidirecional.

Princípio de funcionamento

A busca em largura bidirecional (Bidirectional BFS) é uma versão otimizada do algoritmo BFS, que realiza dois percursos paralelos do gráfico: um a partir do vértice inicial e outro a partir do vértice alvo. Os percursos continuam até que os dois cruzem, o que reduz significativamente o número de vértices e arestas verificadas em comparação com o BFS clássico.

Etapas do algoritmo:

• Inicializar duas filas: uma para o percurso a partir do vértice inicial, outra a partir do vértice alvo.
• Inicializar dois conjuntos de vértices visitados para acompanhar os vértices visitados em ambas as direções.
• Realizar percursos alternados do gráfico a partir das duas filas.
• A cada passo, verificar se os conjuntos de vértices visitados se cruzam. Se sim, um caminho existe.
• O processo continua até que seja encontrado um nó de interseção ou as filas fiquem vazias.

Complexidade de tempo

No melhor caso: O(2 * (V + E)) = O(V + E), onde V é o número de vértices, E é o número de arestas.

O BFS bidirecional geralmente percorre um menor número de vértices em comparação com o BFS unidirecional, especialmente em gráficos grandes.

Complexidade de espaço:

O(V) para armazenamento de duas filas e dois conjuntos de vértices visitados.

Exemplo de implementação de BFS bidirecional

O exemplo é muito longo — o algoritmo é cerca de três vezes mais longo do que a busca unidirecional — por isso não o apresentarei aqui. Quando você realmente precisar, estará em condições de escrevê-lo por conta própria.

8.4 Exemplos de problemas resolvidos com BFS

Exemplos clássicos de problemas resolvidos com BFS:

1. Busca do caminho mais curto em um gráfico não direcionado:

O BFS é usado para encontrar o caminho mais curto (mínimo número de arestas) do vértice inicial ao alvo em um gráfico não direcionado.

Aplicação:

• Em sistemas de navegação para encontrar o caminho mais curto entre os pontos.
• Na análise de redes para encontrar o caminho mais curto para transmissão de dados.

2. Verificação de conectividade do gráfico:

Verificar se o gráfico é conectado, ou seja, se existe um caminho entre qualquer dois vértices.

Aplicação:

• Na análise de redes para verificar a conectividade da rede.
• Na análise de redes sociais para verificar a conectividade de um grupo de usuários.

3. Geração de labirintos:

Uso do BFS para gerar labirintos aleatórios com propriedades específicas.

Aplicação:

• Em aplicativos de jogos para criação de labirintos.
• Em robótica para testar algoritmos de navegação.

4. Busca em largura em árvores:

O BFS é usado para percorrer árvores, para realizar ações em cada nível da árvore (por exemplo, imprimir todos os nós em cada nível).

Aplicação:

• Em problemas de visualização de dados, onde é necessário exibir dados por níveis.
• Em problemas de planejamento, onde ações são necessárias em cada nível da hierarquia.

5. Verificação de bipartição de gráfico:

Verificar se o gráfico é bipartido, ou seja, se é possível dividir os vértices em dois subconjuntos de forma que as arestas existam apenas entre vértices de conjuntos diferentes.

Aplicação:

• Na teoria dos grafos para verificar a bipartição do gráfico.
• Em problemas de coloração de grafos, onde é necessário verificar se é possível colorir o gráfico com duas cores.