Visualizador BFS vs DFS

Veja como BFS e DFS exploram o mesmo grafo de formas diferentes. BFS avança em largura, DFS avança em profundidade.

Valores iniciais — Visualizador BFS vs DFS

Grafo predefinido	Grade 4x4
Nó inicial	0

Altere qualquer controlo acima e os resultados são recalculados.

A carregar a simulação interativa...

BFS acha o caminho mais curto só quando toda aresta custa o mesmo 🖖

O motivo habitual para escolher BFS é que ele devolve a rota mais curta. Essa garantia é mais estreita do que parece: ela vale porque o BFS trata cada aresta como um passo, então na primeira vez que alcança um nó ele necessariamente chegou pelo menor número de saltos. Acrescente custos reais — distâncias de estrada, taxas de transferência, latência — e a garantia se dissolve. O BFS ainda responderá com confiança, e estará errado, porque um caminho de duas arestas caras pode facilmente custar mais que um de cinco arestas baratas. O algoritmo de Dijkstra é o reparo, e é quase exatamente isto: BFS com a fila simples trocada por uma fila de prioridade.

O mesmo mapa, dois estilos de viagem 🖖

Execute os dois lado a lado: visitam exatamente os mesmos vértices e as mesmas arestas, mas por ordens diferentes. A BFS explora toda a vizinhança atual antes de avançar, por isso tem de guardar todos os vértices que aguardam na fronteira. A DFS segue um ramo e regista apenas o caminho que está a percorrer. Na árvore binária, isso corresponde a 8 vértices na fila, contra uma pilha de profundidade 4. Use a BFS quando for provável que a solução esteja perto e a DFS quando o grafo for profundo e convier poupar memória.

Ambos os algoritmos nasceram em labirintos 🖖

Muito antes dos computadores, a DFS já existia como uma regra para percorrer labirintos, publicada pelo matemático francês Charles Pierre Trémaux no século XIX. A BFS chegou bem depois: Edward F. Moore a reinventou em um artigo de 1959 intitulado literalmente The Shortest Path Through a Maze, e Konrad Zuse já a havia esboçado em 1945. Dois pilares da ciência da computação, ambos concebidos originalmente apenas para escapar de um labirinto.

PERCURSO EM GRAFOS — DE QUE ORDEM VOCÊ PRECISA E QUANTO ELA CUSTA?

Em que caso de percurso você está?

BFS e DFS visitam os mesmos vértices e diferem em uma linha de código: uma fila no lugar de uma pilha. Todo o resto decorre disso. A fila se espalha em anéis, então quando o BFS chega pela primeira vez a um vértice ele veio por um caminho com o menor número de arestas. A pilha mergulha, então o DFS alcança a ponta distante mais cedo, mas por rota nenhuma em particular. Qual você quer depende da pergunta — e do formato do grafo, que decide o custo de cada um.

Você precisa do menor número de arestas — BFS, porque visita em camadas de distância FIFO ⇒ min |E|

Uma árvore — ordem por níveis contra pré-ordem, e o custo de memória se inverte BFS: O(w), DFS: O(d)

Uma corrente — as duas ordens coincidem e a escolha deixa de importar deg ≤ 2 ⇒ BFS = DFS

Nem tudo é alcançável — um vértice de partida não basta c(G) > 1

Você precisa do menor número de arestas — BFS, porque visita em camadas de distância

O que você sabe: Um grafo sem pesos e uma pergunta de caminho mínimo. O BFS visita tudo à distância 1, depois tudo à distância 2, de modo que a primeira chegada a um vértice se dá por um caminho mínimo.

Regra: FIFO ⇒ min |E|

Exemplo resolvido: Na malha 4×4 a partir do vértice 0, o BFS visita 0, 1, 4, 2, 5, 8, 3, 6, 9, 12, … — uma frente de onda diagonal. O DFS visita 0, 1, 2, 3, 7, 6, 5, 4, … e só chega ao vértice 4 no oitavo passo.

Abrir este caso: Grade 4x4

Você precisa do menor número de arestas — BFS, porque visita em camadas de distância. O BFS varre para fora em camadas de distância; o DFS serpenteia por um corredor antes de voltar. Um grafo sem pesos e uma pergunta de caminho mínimo. O BFS visita tudo à distância 1, depois tudo à distância 2, de modo que a primeira chegada a um vértice se dá por um caminho mínimo. — O BFS varre para fora em camadas de distância; o DFS serpenteia por um corredor antes de voltar.

Uma árvore — ordem por níveis contra pré-ordem, e o custo de memória se inverte

O que você sabe: Numa árvore as duas ordens têm nome: BFS é a ordem por níveis, DFS é a pré-ordem. Ambos visitam os 15 vértices; o que muda é quanto precisa ser mantido de uma vez.

Regra: BFS: O(w), DFS: O(d)

Exemplo resolvido: O BFS dá 0, 1, 2, 3, …, 14 — nível a nível. O DFS dá 0, 1, 3, 7, 8, 4, 9, 10, 2, … — primeiro pela espinha esquerda. Fila máxima 8, pilha máxima 4.

Abrir este caso: Árvore binária

Uma árvore — ordem por níveis contra pré-ordem, e o custo de memória se inverte. A ordem por níveis preenche cada fileira antes de descer; a pré-ordem corre até uma folha e volta. Numa árvore as duas ordens têm nome: BFS é a ordem por níveis, DFS é a pré-ordem. Ambos visitam os 15 vértices; o que muda é quanto precisa ser mantido de uma vez. — A ordem por níveis preenche cada fileira antes de descer; a pré-ordem corre até uma folha e volta.

Uma corrente — as duas ordens coincidem e a escolha deixa de importar

O que você sabe: Cada vértice tem exatamente um vizinho não visitado, então há um único jeito de seguir. BFS e DFS produzem a mesma sequência e guardam um vértice de cada vez.

Regra: deg ≤ 2 ⇒ BFS = DFS

Exemplo resolvido: Na corrente de 12 vértices ambos visitam 0, 1, 2, …, 11 nessa ordem, e as duas frentes ficam em tamanho 1 do começo ao fim.

Abrir este caso: Cadeia longa

Uma corrente — as duas ordens coincidem e a escolha deixa de importar. Sem nada em que ramificar, os dois percursos andam a mesma linha na mesma ordem. Cada vértice tem exatamente um vizinho não visitado, então há um único jeito de seguir. BFS e DFS produzem a mesma sequência e guardam um vértice de cada vez. — Sem nada em que ramificar, os dois percursos andam a mesma linha na mesma ordem.

Nem tudo é alcançável — um vértice de partida não basta

O que você sabe: O grafo vem em pedaços. Partindo de um vértice, qualquer dos percursos visita só a componente a que esse vértice pertence e então para.

Regra: c(G) > 1

Exemplo resolvido: A partir do vértice 0 do grafo de 10 vértices, tanto o BFS quanto o DFS visitam exatamente 4 vértices e param. Os vértices 4, 5, 6, 7, 8 e 9 nunca são tocados.

Abrir este caso: Desconectado

Nem tudo é alcançável — um vértice de partida não basta. Quatro vértices alcançáveis e seis não: uma partida explora uma componente e nada mais. O grafo vem em pedaços. Partindo de um vértice, qualquer dos percursos visita só a componente a que esse vértice pertence e então para. — Quatro vértices alcançáveis e seis não: uma partida explora uma componente e nada mais.

Referências (2)

Insight block 3 — BFS as a maze algorithm: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.
Trémaux's rule, as it was actually published: É. Lucas, Récréations mathématiques, vol. 1. Gauthier-Villars, Paris, 1882 — Lucas credits the maze-walking procedure to Charles Pierre Trémaux.

Problema resolvido na íntegra

Uma travessia de um labirinto com 16 nós e 16 arestas 5 passos
O labirinto possui 16 nós unidos por 16 arestas. Calcule quantos nós alcança um percurso com início no nó 0, e a que distância o nó 15 está do nó 0. Este é o estado Corredor do labirinto com o nó inicial 0.
1. Escreva o labirinto sob a forma de lista de adjacências antes de fazer qualquer outra coisa. O nó 4 é aquele que vale a pena notar: nem uma única aresta lhe toca, pelo que o seu grau é 0 e nenhum percurso com início noutro local chegará a ele.
  
  $0 : 11 : 0, 2, 52 : 1, 33 : 24 : \emptyset 5 : 1, 6, 96 : 5, 7, 107 : 6, 118 : 9, 12 9 : 5, 8, 1010 : 6, 9, 1411 : 7, 15 12 : 8, 1313 : 12, 1414 : 10, 1315 : 11$
2. A pesquisa em largura organiza o que consegue alcançar em camadas, sendo a camada k constituída por tudo o que é encontrado pela primeira vez a partir da camada k − 1. Construí-las é um fecho e não um percurso — termina-se uma camada por completo antes de abrir a seguinte, e nenhum nó aparece duas vezes.
  
  $L_{0} L_{3} L_{6} = {0} = {3, 6, 9} = {13, 15} L_{1} L_{4} = {1} = {7, 8, 10} L_{2} L_{5} = {2, 5} = {11, 12, 14}$
3. Adicione os tamanhos das camadas. O percurso alcança 15 nós, menos um do que os 16 que o grafo contém, e é por isso que o contador de passos para uma unidade abaixo da contagem de nós.
  
  $1 + 1 + 2 + 3 + 3 + 3 + 2 = 15, n = 16, de g (4) = 0$
4. O nó 15 aparece pela primeira vez na camada 6, e o número de uma camada é uma distância: um nó só é colocado na fila a partir de um nó uma camada acima dele, pelo que nada na camada 6 pode ser alcançado em menos de 6 arestas. O percurso 0-1-5-6-7-11-15 atinge 6, pelo que o limite é exato.
  
  $15 \in L_{6} ⟹ d (0, 15) = 6 : 0 \to 1 \to 5 \to 6 \to 7 \to 11 \to 15$
5. A busca em profundidade não preserva nenhum invariante desse tipo. Se, no vértice 1, o percurso visitar 5 antes de 2; no vértice 5, visitar 9 antes de 6; e, no vértice 9, visitar 8 antes de 10, estará sempre a fazer escolhas legítimas entre vizinhos ainda não visitados, mas enveredará pelo longo corredor e só retrocederá quando não puder avançar mais. Chegará ao vértice 15 no extremo de um caminho com 12 arestas, uma resposta perfeitamente válida para a questão da alcançabilidade.
  
  $0 \to 1 \to 5 \to 9 \to 8 \to 12 \to 13 \to 14 \to 10 \to 6 \to 7 \to 11 \to 15 ⟹ ℓ = 12$
Resposta

O nó 15 situa-se a 6 arestas do início, e um percurso em profundidade pode apresentar-lhe uma rota de 12 para o mesmo local. O fator 2 não é a parte interessante; o interessante é de onde pode sequer vir um atalho. A componente alcançável contém 15 nós, pelo que qualquer árvore de cobertura da mesma utiliza 14 arestas — e o labirinto tem 16, o que significa que exatamente 2 arestas são excedentárias. Elimine essas 2 e o que resta é uma árvore, onde existe precisamente um caminho entre qualquer par de nós, pelo que os dois painéis concordariam então em todas as distâncias e difeririam apenas na ordem em que percorrem os nós. Cada divergência quanto à distância entre eles remonta a essas 2 arestas extra. É também a razão pela qual a pesquisa em profundidade é o hábito mais económico quando a questão é meramente se um nó é alcançável, e o hábito errado no momento em que a questão passa a ser a que distância.

$∣ E ∣ - (∣ V ∣ - 1) = 16 - (15 - 1) = 2$

Pela equipa 42Math · Atualizado 2026-07-27

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

Grade 4x4 - Grelha 4×4: a BFS avança em camadas diagonais de 1, 2, 3, 4, 3, 2, 1 vértices e chega ao canto oposto em 6 passos.
Corredor de labirinto - A DFS percorre 12 corredores antes de chegar ao vértice 15. A BFS demonstra que bastam 6. O mesmo labirinto, o dobro do percurso.
Grafo estrela - Nove raios, com todos os vértices a um passo do centro. A busca em profundidade não encontra por onde aprofundar, por isso devolve a mesma ordem que a BFS.
Cadeia longa - Doze vértices em linha: as ordens voltam a coincidir, mas aqui cada algoritmo guarda um vértice de cada vez, contra os nove da estrela.
Árvore binária - Árvore binária completa: a fila da BFS atinge 8 vértices, todo o nível inferior, enquanto a pilha da DFS nunca ultrapassa 4.
Desconectado - Dois quadrados e dois vértices isolados. Um percurso iniciado no vértice 0 alcança 4 dos 10; nenhuma busca encontra os restantes.
Grafo denso - 8 vértices, 13 arestas, e o vértice 7 continua a uma distância de 3 passos: nesta dimensão, um grafo denso não põe tudo perto.