Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices (origem, destino), use repetição e seleção para determinar a menor distância (número mínimo de arestas) entre eles.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
BFS em lista de adjacência: inicialize fila Q; dist[v]= -1 para todos; dist[orig]=0; enqueue(orig); while Q não vazio: v=dequeue(Q); for u em adj[v]: if dist[u]==-1 then dist[u]=dist[v]+1; pred[u]=v; enqueue(u); if u==destino break; Ao final, dist[destino] é a menor distância; reconstrua caminho por pred.
Explicação
O algoritmo utiliza a busca em largura (BFS), que é ideal para encontrar a menor distância em um grafo não ponderado, já que explora todos os vértices a uma certa distância antes de passar para os próximos. A inicialização das distâncias e a utilização de uma fila garantem que cada vértice é visitado na ordem correta, permitindo que a distância mínima seja calculada de forma eficiente. Além disso, a reconstrução do caminho através do vetor de predecessores permite identificar a sequência de vértices que compõem a rota mais curta.
Raio-X da questão
algoritmo de busca em grafos
avaliacao
estrutura de dados em grafos · pseudocódigo
Revisar algoritmos de busca em grafos e suas implementações.
O aluno pode confundir a lógica de repetição e seleção, não aplicando corretamente as condições para encontrar a menor distância entre os vértices.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
- Descreva um algoritmo em pseudocódigo que, dado um grafo dirigido acíclico e dois vértices s e t, encontra um caminho de…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog