<\> Casa do Dev
Notícias abrir
Ferramentas abrir
Vagas abrir
Aprender abrir
Comunidade abrir
Guia de Compras abrir

BFS: o que é, como funciona e implementação em Python (com código)

DA

10 min

Entusiasta das Tecnologias

BFS: o que é, como funciona e implementação em Python (com código)

Guia do algoritmo BFS: funcionamento por níveis, implementação em Python com deque, caminho mais curto, complexidade O(V+E) e diferenças para o DFS.

Neste artigo

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:

  1. Definição da origem: escolhe-se o nó inicial onde a busca começa.
  2. Marcação de visita: a origem é marcada como visitada e enfileirada.
  3. Processamento: enquanto a fila não estiver vazia, o algoritmo remove o primeiro nó, processa-o e examina seus vizinhos.
  4. Enfileiramento dos vizinhos: cada vizinho ainda não visitado é marcado como visitado e adicionado ao fim da fila.
  5. 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.

Produtos relacionados

Este conteúdo tem links de afiliado: se você comprar por eles, podemos receber uma comissão sem custo extra para você. A escolha dos produtos segue critérios próprios e não é influenciada por comissão.

O que você achou deste artigo?

Responda a Pergunta do Dia Teste seu conhecimento e mantenha sua streak. Crie seu Dev Card público Perfil dev compartilhável em um único link.

Depois dessa formação...

Veja vagas em tecnologia →

Vagas relacionadas

Ver todas as vagas →
DA

Escrito por

Dagmar Cirino

Entusiasta das Tecnologias

Atualizado em 01/11/2026 •

Sou o Cirino, e desenvolvo soluções e produtos utilizando linguagens de programação e ferramentas de analytics e monitoração baseadas em Cloud. Trabalho com tecnologia desde 2010,...

Ver perfil do autor

COMPARTILHAR