Árvores e grafos: como percorrer

O problema

Tem gente que vê árvore e grafo no enunciado e já assume que o problema ficou dez vezes mais difícil.

Às vezes ficou.

Mas muitas vezes o drama vem mais da aparência da estrutura do que da lógica necessária.

Boa parte dessas perguntas começa em algo bem direto:

• como eu visito os nós?
• em que ordem?
• como evito me perder ou revisitar à toa?

Se essa camada não estiver clara, qualquer detalhe extra vira caos.

Modelo mental

Árvore e grafo são estruturas de conexão.

A grande diferença é que a árvore costuma vir com mais ordem:

• uma raiz
• relação pai-filho
• nenhum ciclo

O grafo é mais geral:

• pode ter ciclo
• pode não ter raiz
• pode ser direcionado ou não
• pode ter várias formas de chegar no mesmo nó

Por isso, muita solução boa começa pensando em travessia.

Duas famílias dominam:

• DFS: depth-first search, exploração em profundidade
• BFS: breadth-first search, exploração em largura

Se quiser uma frase simples:

Antes de resolver a pergunta sofisticada, descubra qual caminhada pela estrutura faz mais sentido.

Quebrando o problema

DFS, em português claro

DFS tenta ir fundo antes de voltar.

É como entrar num corredor e continuar seguindo enquanto dá, voltando só quando bate em saída sem continuação.

Ela aparece muito em:

• altura de árvore
• validação estrutural
• procura de caminho
• exploração de componente conectado
• perguntas em que a informação vem da subárvore

Pode ser feita com:

• recursão
• stack explícita

BFS, em português claro

BFS explora por camadas.

Primeiro tudo que está perto.

Depois o que está a um passo de distância.

Depois o que está a dois passos.

Ela aparece muito em:

• menor caminho em grafo sem peso
• distância por níveis
• travessia por níveis em árvore
• perguntas em que a primeira vez que você encontra algo já importa

Normalmente usa queue.

O papel do visited

Em árvore, muitas vezes você nem pensa nisso porque não há ciclo.

Em grafo, esquecer visited costuma ser pedir para:

• visitar nó repetido
• entrar em loop
• inflar complexidade sem perceber

Visited não é detalhe burocrático.

É parte da definição da travessia quando a estrutura permite retorno.

Transforme a pergunta em travessia + condição

Esse truque ajuda muito.

Exemplos:

• “encontre a profundidade máxima” → DFS + calcular profundidade
• “descubra se existe caminho” → DFS ou BFS + condição de chegada
• “menor número de passos” → BFS + distância
• “quantos grupos conectados existem?” → travessia repetida + contagem de componentes

Muita questão assustadora fica menor quando você a traduz assim.

Exemplo simples

Pegue uma árvore binária e a pergunta:

Qual a profundidade máxima?

A solução mais natural costuma ser DFS.

Por quê?

Porque a resposta de um nó depende da profundidade máxima das subárvores dele.

O raciocínio vira:

1. se o nó é nulo, profundidade zero
2. calcule profundidade da esquerda
3. calcule profundidade da direita
4. pegue a maior e some um

Agora compare com uma pergunta diferente:

Qual a distância mínima entre o nó inicial e outro nó em um grafo sem peso?

Aqui BFS costuma ser mais natural.

Porque ela avança por camadas.

A primeira vez que chega no destino já representa o menor número de arestas.

O ponto não é decorar “profundidade usa DFS, menor caminho sem peso usa BFS”.

O ponto é perceber que a ordem da exploração responde melhor à pergunta.

Erros comuns

• Ficar travado na estrutura e esquecer que a travessia é a primeira decisão.
• Usar DFS onde BFS deixaria a resposta mais direta, ou o contrário.
• Esquecer visited em grafo com ciclo.
• Misturar árvore e grafo como se fossem idênticos em todas as propriedades.
• Sair codando a travessia sem dizer o que está acumulando em cada passo.

Como um senior pensa

Quem já tem mais repertório costuma desdramatizar esse tipo de problema bem rápido.

O pensamento costuma ser:

• qual estrutura eu realmente tenho aqui?
• tem ciclo?
• tem raiz?
• preciso de menor distância ou só explorar tudo?
• a resposta depende da subestrutura ou da ordem por camada?

Essa forma de pensar é importante porque evita “usar a travessia que eu lembro melhor”.

E isso vale fora da entrevista também.

Dependência entre serviços, navegação de árvore de componentes, workflow, grafo de permissões, topologia de jobs. Tudo isso reaproveita a mesma cabeça de travessia.

O que o entrevistador quer ver

Ele quer ver se você:

• reconhece a travessia adequada
• entende a diferença entre BFS e DFS
• sabe quando visited é obrigatório
• consegue explicar o estado carregado em cada passo

Se você conseguir dizer “isso aqui é travessia mais condição, e BFS faz mais sentido porque quero menor distância em grafo sem peso”, já está muito melhor do que quem só despeja template.

Árvore e grafo ficam menos assustadores quando você para de olhar a estrutura inteira e passa a olhar a próxima visita.

Em muita pergunta, a metade da solução é só escolher a caminhada certa.