Por que guardar o pai, e não o caminho inteiro em cada ponto?

Guardar só o pai gasta bem menos memória: cada vértice precisa lembrar de um único antecessor, não da lista toda até ali. No fim, seguir os pais de trás para frente reconstrói o caminho sob demanda. Guardar o caminho completo em cada ponto funcionaria, mas repetiria muita informação e pesaria à toa em redes grandes.

Por que a rota sai de trás para frente e precisa ser invertida?

Porque seguimos os pais partindo do destino: primeiro o destino, depois o pai dele, depois o pai do pai, até a origem. Essa ordem é a inversa do trajeto real. Invertendo a sequência (ou inserindo cada ponto no início da lista), a rota fica na ordem natural, da origem ao destino.

O teste de mesa não é perda de tempo se dá para rodar no computador?

Não. O teste de mesa força você a entender o algoritmo por dentro, acompanhando fila, visitados e pais mudando. Ele pega erros de lógica que um teste apressado no computador pode esconder, e ensina a raciocinar sobre casos de borda. Rodar no computador confirma; o teste de mesa é onde você realmente compreende.

O que a função deve devolver quando não existe caminho?

Uma resposta clara de que não há rota, como uma lista vazia ou um aviso, nunca um travamento ou um resultado inventado. O destino inalcançável é uma situação legítima: a busca percorre tudo que consegue e, se o destino não aparece, a fila esvazia. Tratar esse caso com honestidade é parte de um programa correto.

Preciso mesmo cuidar do caso origem igual a destino?

Sim, porque é um caso simples que muitos programas erram. Se você já está no destino, a rota é só aquele ponto e o número de passos é zero. Um programa que não trata isso pode devolver uma resposta estranha ou vazia. Cuidar dos casos de borda é o que torna a solução confiável, não apenas funcional no caso comum.

Esse mesmo programa serve para um labirinto?

Serve. Modele cada casa livre do labirinto como um vértice e cada passo entre casas vizinhas como uma aresta, e a mesma busca em largura acha a saída pelo menor número de passos, reconstruindo o caminho pelos pais. Foi essa generalidade que justificou modelar como grafo desde a primeira aula do projeto.

Módulo 15 - Projeto final: Mapa de Rotas

Montando o programa completo

9 min de leitura · por Cesar Gargiulo, revisado pela equipe ValorFinal e GuardiaSec · Atualizado em 12/07/2026

O que você vai aprender

Juntar grafo, fila e conjunto de visitados num programa único.
Guardar o pai de cada vértice para poder reconstruir o caminho.
Reconstruir a rota seguindo os pais do destino até a origem.
Fazer um teste de mesa e caçar um bug da busca em largura.

Juntar as peças

A busca em largura da aula anterior responde se dá para chegar, mas o Mapa de Rotas precisa de mais: a lista de estações do trajeto. A peça que faltava é pequena e engenhosa. Toda vez que a busca descobre um vizinho novo, ela anota quem o descobriu, o pai daquele vértice. Se Parque foi visto pela primeira vez a partir de Norte, guardamos pai de Parque igual a Norte. No fim, quando a busca chega ao destino, temos uma trilha de migalhas: cada ponto sabe de quem veio. Basta seguir essas migalhas do destino para trás, de pai em pai, até cair na origem. Essa sequência, invertida, é o caminho.

funcao achar_rota(grafo, origem, destino)
  fila <- [origem]
  visitados <- {origem}
  pai <- {origem: nulo}
  enquanto fila nao vazia faca
    atual <- desenfileirar(fila)
    se atual = destino entao
      // reconstruir seguindo os pais de tras para frente
      rota <- []
      no <- destino
      enquanto no diferente de nulo faca
        inserir_no_inicio(rota, no)
        no <- pai[no]
      fim
      retorne rota
    para cada vizinho de grafo[atual] faca
      se vizinho nao esta em visitados entao
        adicionar(visitados, vizinho)
        pai[vizinho] <- atual
        enfileirar(fila, vizinho)
      fim
    fim
  fim
  retorne "sem rota"
fim

O mapa de pais nasce junto com os visitados. Ao achar o destino, seguir os pais de trás para frente monta a rota.

Teste de mesa numa rede pequena

Rodar de cabeça numa rede pequena é a melhor forma de confiar no programa. Use o grafo do metrô: Centro liga a Norte e Feira; Norte liga a Centro e Parque; Feira liga a Centro e Porto; Parque liga a Norte e Porto; Porto liga a Feira e Parque. Procure a rota de Centro a Porto. A busca começa com Centro na fila e como visitado, pai de Centro nulo. Tira Centro, descobre Norte (pai Norte igual a Centro) e Feira (pai Feira igual a Centro), e enfileira os dois. Tira Norte, descobre Parque (pai Parque igual a Norte). Tira Feira, descobre Porto (pai Porto igual a Feira): é o destino. Reconstruindo de trás para frente, Porto veio de Feira, Feira veio de Centro, Centro é a origem. Invertendo, a rota é Centro, Feira, Porto, com dois trechos, o menor possível.

Diagrama do teste de mesa: à esquerda o grafo do metrô com cinco estações. À direita, três colunas evoluindo por iteração mostram o estado da fila, do conjunto de visitados e do mapa de pais. Setas destacam o caminho reconstruído Porto para Feira para Centro, e abaixo a rota final Centro, Feira, Porto invertida. — Acompanhando fila, visitados e pais, o teste de mesa confirma a rota Centro, Feira, Porto.

🎮 Jogo da aula

O visitado que sumiu

Este trecho deveria marcar cada vizinho como visitado ao descobri-lo, mas tem um erro que faz a busca repetir pontos e travar. Toque na linha do bug.

Quando não há rota e outros cuidados

Um bom programa não trata só o caso feliz. Se o destino estiver numa parte desconectada da rede, a fila esvazia sem que o destino apareça, e a função devolve sem rota em vez de travar ou mentir. Vale também cuidar dos casos de borda: origem igual ao destino devolve uma rota de um ponto só, sem passos; um destino que nem existe no grafo deve ser rejeitado logo no começo. Esses detalhes separam um rascunho de um programa confiável. E o teste de mesa é o melhor aliado aqui, porque força você a percorrer justamente as situações estranhas que um teste rápido no computador poderia não cobrir. Programa que passa no teste de mesa nos casos difíceis costuma se comportar bem no computador.

Teste rápido

Como o programa reconstrói a lista de pontos do caminho, e não apenas descobre a distância?

Perguntas frequentes

Por que guardar o pai, e não o caminho inteiro em cada ponto?: Guardar só o pai gasta bem menos memória: cada vértice precisa lembrar de um único antecessor, não da lista toda até ali. No fim, seguir os pais de trás para frente reconstrói o caminho sob demanda. Guardar o caminho completo em cada ponto funcionaria, mas repetiria muita informação e pesaria à toa em redes grandes.
Por que a rota sai de trás para frente e precisa ser invertida?: Porque seguimos os pais partindo do destino: primeiro o destino, depois o pai dele, depois o pai do pai, até a origem. Essa ordem é a inversa do trajeto real. Invertendo a sequência (ou inserindo cada ponto no início da lista), a rota fica na ordem natural, da origem ao destino.
O teste de mesa não é perda de tempo se dá para rodar no computador?: Não. O teste de mesa força você a entender o algoritmo por dentro, acompanhando fila, visitados e pais mudando. Ele pega erros de lógica que um teste apressado no computador pode esconder, e ensina a raciocinar sobre casos de borda. Rodar no computador confirma; o teste de mesa é onde você realmente compreende.
O que a função deve devolver quando não existe caminho?: Uma resposta clara de que não há rota, como uma lista vazia ou um aviso, nunca um travamento ou um resultado inventado. O destino inalcançável é uma situação legítima: a busca percorre tudo que consegue e, se o destino não aparece, a fila esvazia. Tratar esse caso com honestidade é parte de um programa correto.
Preciso mesmo cuidar do caso origem igual a destino?: Sim, porque é um caso simples que muitos programas erram. Se você já está no destino, a rota é só aquele ponto e o número de passos é zero. Um programa que não trata isso pode devolver uma resposta estranha ou vazia. Cuidar dos casos de borda é o que torna a solução confiável, não apenas funcional no caso comum.
Esse mesmo programa serve para um labirinto?: Serve. Modele cada casa livre do labirinto como um vértice e cada passo entre casas vizinhas como uma aresta, e a mesma busca em largura acha a saída pelo menor número de passos, reconstruindo o caminho pelos pais. Foi essa generalidade que justificou modelar como grafo desde a primeira aula do projeto.

Fontes

Seu progresso fica salvo neste aparelho. Assinantes sincronizam entre os aparelhos.

← Achar o menor caminho com busca em largura Concluir e avançar →