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
- Um aplicativo de voz transforma fala em texto usando dados e algoritmo. Selecione o exemplo de inteligencia artificial.
- Crie um algoritmo em pseudocódigo que solicite números ao usuário até que digite 0; para cada número conte quantos são…
- Ao decompor um algoritmo que calcula o produto de elementos de uma lista de dados, qual subtarefa isola a inicialização…
- Projete em pseudocódigo um algoritmo que, dada uma lista de leituras (lista[1..n]) e um limiar T, retorne o índice da…
- Projete um autômato baseado em eventos para tocar o sinal de entrada e saída das aulas numa escola: descreva estados…
- Elabore um algoritmo em passos que use a variável 'umidade' lida de um sensor de solo (dispositivo de entrada) para…
🔎 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