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.
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.
queue = deque(["A"])🪨 Jogue a pedra em Anode = queue.popleft()🌊 Pegue o próximo nó por ordem de distânciaif neighbor not in visited:🔎 Ainda não foi alcançado?queue.append(neighbor)➕ Adicione ao próximo anelA 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
queueguarda os nós esperando para serem explorados, os mais antigos primeiro.visitedregistra os nós já encontrados, então nenhum é adicionado duas vezes e ciclos não fazem laço infinito.node = queue.popleft()pega o próximo nó; seus vizinhos não visitados entram no fim da fila.ordermostra 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
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)
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.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Marcar nós como visitados tarde demais
Se um nó só é marcado quando sai da fila, ele pode ser adicionado muitas vezes.
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
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.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Médio
- Diâmetro da Árvore Uma árvore é um grafo não direcionado, conexo e sem ciclos. Médio
- Count Islands Count groups of connected land cells in a grid. Médio