Algoritmos em Python

Busca em largura (BFS) em Python

Nesta lição, você vai percorrer um grafo nível por nível com a busca em largura e uma fila deque.

  • Intermediário
  • 3 min de leitura
  • 1 exemplo executável

Introdução

O problema

Quantos passos são necessários para ir de uma pessoa a outra em uma rede social, ou de um quadrado de um labirinto até a saída? A busca em largura explora em anéis de distância, então a primeira vez que chega a um nó é por um caminho mais curto.

Pense assim

A busca em largura é como ondas em um lago. Jogue uma pedra no início e a onda alcança primeiro tudo a um passo de distância, depois tudo a dois passos, e assim por diante. Nada mais longe é tocado antes de tudo o que está mais perto ser alcançado.

Das ondas no lago ao código
queue = deque(["A"])🪨 Jogue a pedra em A
node = queue.popleft()🌊 Pegue o próximo nó por ordem de distância
if neighbor not in visited:🔎 Ainda não foi alcançado?
queue.append(neighbor)➕ Adicione ao próximo anel
Os nós mais próximos primeiro, usando uma fila.
Em uma frase

A busca em largura (BFS, breadth-first search) visita um grafo nível por nível a partir de um nó inicial, usando uma fila. Assim ela encontra caminhos mais curtos em grafos sem pesos.

Pontos-chave

  1. queue guarda os nós esperando para serem explorados, os mais antigos primeiro.
  2. visited registra os nós já encontrados, então nenhum é adicionado duas vezes e ciclos não fazem laço infinito.
  3. node = queue.popleft() pega o próximo nó; seus vizinhos não visitados entram no fim da fila.
  4. order mostra A, depois seus vizinhos B e C, depois D e E um nível adiante.

Quando usar?

  • Caminhos mais curtos em grafos sem pesos, grades e labirintos.
  • Graus de separação em redes sociais.
  • Rastreadores da web e encontrar tudo o que é alcançável a partir de um ponto.

Quando não é preciso

  • As arestas têm custos diferentes, como distâncias de estradas: use o algoritmo de Dijkstra.
  • Você precisa explorar um caminho inteiro antes dos outros, como no backtracking: use busca em profundidade.

Visualizador de Busca em largura (BFS) em Python

O(V + E)

Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.

Código de exemplo

Executar código →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

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

print(order)
Gerar um botão Run para este exemplo

Resultado da execução

['A', 'B', 'C', 'D', 'E']

Explicação do código

A fila queue guarda os vértices que esperam ser visitados, e eles saem na mesma ordem em que entraram. O conjunto visited registra os vértices já encontrados para não visitar o mesmo vértice várias vezes quando o grafo tem ciclos. A ordem de visita é A, B, C, D, E, e a complexidade é O(V + E), em que V é o número de vértices e E o de arestas.

Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.

Exercícios práticos

Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Marcar nós como visitados tarde demais

Se um nó só é marcado quando sai da fila, ele pode ser adicionado muitas vezes.

Problema
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Correção
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

Terminou esta lição?

Marque como aprendida para acompanhar seu progresso.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios