Neste artigo
- O que significa BFS e para que ele serve?
- Como funciona o algoritmo BFS passo a passo?
- Como implementar BFS em Python?
- Encontrar o caminho mais curto com BFS
- Qual é a complexidade de tempo e espaço do BFS?
- Qual a diferença entre BFS e DFS?
- Quais são as aplicações reais do BFS?
- Como transformar o domínio de BFS em vantagem na carreira?
- O que significa BFS?
- O BFS sempre encontra o caminho mais curto?
- Qual é a complexidade do algoritmo BFS?
- Qual a diferença entre BFS e DFS?
- O BFS pode ser implementado de forma recursiva?
O BFS (Breadth-First Search, busca em largura) é um algoritmo de travessia de grafos que explora os nós nível por nível, partindo de uma origem e avançando em ondas de vizinhos. Com uma fila e um registro de visitados, ele garante o caminho com o menor número de arestas em qualquer grafo sem pesos, o que o torna presença constante em entrevistas técnicas e em sistemas reais de redes e busca. Se você está organizando esses estudos, comece pelo guia sobre o que são estruturas de dados e algoritmos (DSA).
Neste guia, você vai ver o significado do termo, o funcionamento passo a passo, a implementação completa em Python com a fila deques, a reconstrução do caminho mais curto, a comparação com o DFS e as aplicações que aparecem no mercado de trabalho.
O que significa BFS e para que ele serve?
BFS é a sigla de Breadth-First Search, que em português vira busca em largura ou busca por níveis. Em vez de seguir um caminho até o fim antes de voltar, o algoritmo visita todos os vizinhos diretos da origem, depois todos os vizinhos desses vizinhos, e assim por diante. A imagem mental mais útil é a de uma onda se espalhando pela superfície de um lago.
O uso mais importante é encontrar o caminho mais curto, medido em número de arestas, em grafos não ponderados. Isso inclui redes de amizade, mapas de dependências, labirintos sem custo por célula e grafos de configuração de estados. Em grafos com pesos diferentes nas arestas, o BFS deixa de ser a escolha correta e o Dijkstra assume o lugar.
ℹ️ Info: a representação mais comum de um grafo em Python é a lista de adjacência: um dicionário que mapeia cada nó à lista de seus vizinhos. É essa estrutura que os exemplos deste artigo usam.
Como funciona o algoritmo BFS passo a passo?
A mecânica inteira se apoia em duas estruturas: uma fila do tipo FIFO (First-In, First-Out) e um conjunto de nós já visitados. A fila garante a ordem por nível, porque o primeiro nó a entrar é o primeiro a ser processado. O conjunto de visitados impede loops infinitos em grafos com ciclos, que são a regra em sistemas reais.
O fluxo de execução segue estas etapas:
- Definição da origem: escolhe-se o nó inicial onde a busca começa.
- Marcação de visita: a origem é marcada como visitada e enfileirada.
- Processamento: enquanto a fila não estiver vazia, o algoritmo remove o primeiro nó, processa-o e examina seus vizinhos.
- Enfileiramento dos vizinhos: cada vizinho ainda não visitado é marcado como visitado e adicionado ao fim da fila.
- Encerramento: quando a fila esvazia, todos os nós alcançáveis a partir da origem foram explorados.
Detalhe importante: marcar o vizinho como visitado no momento do enfileiramento, e não quando ele sai da fila, evita duplicatas na fila e economiza memória em grafos densos. Essa é uma das pegadinhas mais cobradas em entrevistas, junto com a escolha errada da estrutura de fila, que o próximo bloco resolve.
Como implementar BFS em Python?
A implementação idiomática usa a classe deque do módulo collections, que oferece inserção e remoção nas duas extremidades em tempo constante. Uma lista comum até funciona, mas pop(0) desloca todos os elementos e degrada a performance para O(n) por remoção, o que estraga a complexidade do algoritmo. A documentação oficial do Python detalha o custo das operações de deque.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
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)
return order
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print(bfs(graph, 'A')) # Saída: ['A', 'B', 'C', 'D', 'E', 'F']
A saída mostra a travessia horizontal em ação: primeiro a origem A, depois seus vizinhos B e C, e só então os vizinhos de nível 3, D, E e F. Note que E aponta para F, mas F é enfileirado a partir de C antes de E ser processado, e a verificação de visitados impede a repetição.
Encontrar o caminho mais curto com BFS
A mesma estrutura com um pequeno acréscimo devolve o caminho mais curto: basta guardar, para cada nó visitado, quem o descobriu. Esse mapa de predecessores (parents) forma uma árvore BFS, e o caminho até qualquer nó é a sequência de predecessores lida de trás para frente.
from collections import deque
def bfs_caminho(graph, start, goal):
parents = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal:
path = []
while node is not None:
path.append(node)
node = parents[node]
return path[::-1]
for neighbor in graph[node]:
if neighbor not in parents:
parents[neighbor] = node
queue.append(neighbor)
return None
print(bfs_caminho(graph, 'A', 'F')) # Saída: ['A', 'C', 'F']
O caminho de A até F tem duas arestas por causa da ligação direta de C. Note que o teste de destino acontece quando o nó sai da fila, e a condição de parada precoce economiza varredura desnecessária em grafos grandes.
Qual é a complexidade de tempo e espaço do BFS?
Em tempo, o BFS custa O(V + E), onde V é o número de vértices e E o número de arestas. Cada nó entra na fila no máximo uma vez e cada aresta é examinada no máximo duas vezes, uma por extremidade. Em espaço, o algoritmo guarda todo o nível em expansão na memória, o que dá O(V) no pior caso.
Esse consumo de memória é o preço da garantia de caminho mínimo. Em grafos com fator de ramificação alto, com muitos vizinhos por nó, a fila pode acumular um nível inteiro antes de avançar. Em árvores de busca de jogos, por exemplo, essa explosão é real e costuma empurrar a implementação para variações com limite de profundidade ou algoritmos de custo uniforme.
Qual a diferença entre BFS e DFS?
A diferença está na ordem de visita e na estrutura de controle. O BFS usa fila e varre por camadas; o DFS usa pilha ou recursão e desce um ramo até o fim antes de retroceder. A consequência prática: BFS responde "qual o caminho com menos arestas?", DFS responde "existe um caminho?" e "quais são todos os caminhos?".
| Característica | BFS | DFS |
|---|---|---|
| Estrutura de controle | Fila (FIFO) | Pilha (LIFO) ou recursão |
| Ordem de visita | Por níveis, em largura | Por ramos, em profundidade |
| Caminho mais curto sem pesos | Garantido | Não garantido |
| Consumo de memória | Maior: guarda o nível atual | Menor: guarda o caminho atual |
| Uso típico | Rota mínima, níveis de conexão | Ciclos, ordenação topológica, labirintos |
Na resolução de dependências de pacotes, o DFS aparece no rastreamento de cadeias do npm e do pip, inclusive na detecção de dependências circulares. Já os crawlers dos motores de busca preferem a lógica de largura para indexar a página inicial e seus links diretos antes de descer aos níveis seguintes. A regra de bolso: peso uniforme e resposta de menor distância pedem BFS; exploração exaustiva de ramos pede DFS.
Quais são as aplicações reais do BFS?
O algoritmo sustenta funcionalidades que você usa todos os dias, e citá-las com precisão é o que separa a resposta de entrevista mediana da boa resposta:
- Redes sociais: o cálculo de graus de separação entre usuários, como os níveis de conexão do LinkedIn, é travessia em largura direta.
- Roteamento de redes: encontrar a rota com menos saltos entre equipamentos reduz latência em topologias sem métrica de custo.
- Jogos e robótica: a sequência mínima de movimentos até um estado objetivo é um problema de caminho mais curto em grafo de estados.
- Coleta de lixo: varreduras de alcançabilidade a partir das raízes seguem a mesma lógica para decidir quais objetos ficam na memória.
- Bancos de grafos: consultas de relacionamento em modelos de recomendação e detecção de fraude rodam sobre travessias desse tipo, tema do bootcamp de Neo4j e análise de grafos.
Para quem treina para processos seletivos, o caminho é resolver problemas clássicos de grafos com esse algoritmo e registrar o raciocínio. Nosso material de lógica para entrevistas técnicas com LeetCode organiza essa prática, e a estratégia de estudo sem decoreba está no guia de preparação para entrevista técnica.
Como transformar o domínio de BFS em vantagem na carreira?
Implementar BFS de memória e explicar a escolha dele diante de alternativas demonstra maturidade de engenharia, e é exatamente isso que avaliadores procuram em níveis pleno. Um exercício produtivo é portar a implementação para uma grade bidimensional, o formato de boa parte dos problemas de labirinto, trocando a lista de vizinhos pelos quatro deslocamentos possíveis. O leque de estruturas envolvidas amplia: quem quiser seguir na teoria, o guia de estruturas de dados e algoritmos mapeia o que vale dominar, e a lista duplamente encadeada mostra outra estrutura com operações em O(1) nas extremidades.
O próximo degrau natural é o algoritmo de Dijkstra, que mantém a lógica de expansão do BFS e adiciona uma fila de prioridade para grafos com pesos. Dominar os dois cobre praticamente todo o espectro de perguntas de caminho mínimo em processos seletivos e em sistemas de logística e roteamento.
Perguntas frequentes
O que significa BFS?
BFS é a sigla em inglês de Breadth-First Search, ou busca em largura. É um algoritmo de travessia de grafos e árvores que visita os nós por níveis, usando uma fila, do mais próximo ao mais distante da origem.
O BFS sempre encontra o caminho mais curto?
Sim, desde que o grafo não tenha pesos nas arestas. Em grafos ponderados, o BFS encontra o caminho com menos arestas, mas não o de menor custo total; nesse caso, o algoritmo correto é o Dijkstra.
Qual é a complexidade do algoritmo BFS?
O tempo é O(V + E), com V vértices e E arestas, porque cada nó e cada aresta são processados uma quantidade limitada de vezes. O espaço é O(V), pois a fila e o conjunto de visitados podem acumular um nível inteiro do grafo.
Qual a diferença entre BFS e DFS?
O BFS explora em largura com uma fila e garante o caminho mínimo sem pesos. O DFS explora em profundidade com pilha ou recursão, consome menos memória e serve para explorar todos os caminhos, detectar ciclos e ordenar topologicamente.
O BFS pode ser implementado de forma recursiva?
Não de forma natural. A estrutura de fila é iterativa, e forçar recursão troca a simplicidade por camadas de chamadas desnecessárias. A recursão é a ferramenta natural do DFS, que usa a pilha de chamadas como estrutura de controle.