Percursos de árvore (DFS e BFS)

Percorrer uma árvore

Uma árvore guarda os dados em uma hierarquia de nós, mas muitas vezes precisamos visitá-los todos: para buscar, somar, imprimir ou transformar. Há duas estratégias clássicas, e a diferença é a ordem em que os nós são visitados.

Imagine que você explora um prédio de salas conectadas. Você pode entrar por um corredor até o fim antes de voltar (profundidade), ou checar primeiro todas as portas do seu andar antes de descer para o seguinte (largura).

DFS — Percurso em profundidade (Depth-First Search)

O DFS desce por um ramo até o fundo antes de retroceder e tentar o seguinte. Expressa-se de forma muito natural com recursão: você visita o nó e depois chama a si mesmo sobre cada filho.

function dfs(no, visitar) {
  visitar(no.valor);
  for (const filho of no.filhos) {
    dfs(filho, visitar);
  }
}

A recursão usa por baixo a pilha de chamadas: cada chamada espera que terminem as de seus filhos. Por isso DFS e "pilha" andam de mãos dadas.

BFS — Percurso em largura (Breadth-First Search)

O BFS visita os nós por níveis: primeiro a raiz, depois todos os seus filhos, depois os netos... Para conseguir isso usa-se uma fila (FIFO): colocamos a raiz, e enquanto a fila não estiver vazia, retiramos um nó, o visitamos e enfileiramos seus filhos ao final.

function bfs(raiz, visitar) {
  const fila = [raiz];
  while (fila.length > 0) {
    const no = fila.shift(); // retira o primeiro (FIFO)
    visitar(no.valor);
    for (const filho of no.filhos) {
      fila.push(filho); // os filhos esperam sua vez ao final
    }
  }
}

Qual eu escolho?

• DFS: quando você quer explorar caminhos completos (buscar uma rota, somar um ramo inteiro). Mais simples de escrever com recursão.
• BFS: quando importa a proximidade da raiz (o caminho mais curto em número de passos, processar nível a nível).

Exemplos

DFS recursivo: visita ramos completos

const raiz = { valor: "A", filhos: [
  { valor: "B", filhos: [{ valor: "D", filhos: [] }, { valor: "E", filhos: [] }] },
  { valor: "C", filhos: [] },
]};
const ordem = [];
function dfs(no) {
  ordem.push(no.valor);
  for (const filho of no.filhos) dfs(filho);
}
dfs(raiz);
console.log(ordem.join(" -> ")); // A -> B -> D -> E -> C

BFS com fila: visita por níveis

const raiz = { valor: "A", filhos: [
  { valor: "B", filhos: [{ valor: "D", filhos: [] }, { valor: "E", filhos: [] }] },
  { valor: "C", filhos: [] },
]};
const ordem = [];
const fila = [raiz];
while (fila.length > 0) {
  const no = fila.shift();
  ordem.push(no.valor);
  for (const filho of no.filhos) fila.push(filho);
}
console.log(ordem.join(" -> ")); // A -> B -> C -> D -> E