Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem). Proponha uma representação em memória adequada e descreva dois algoritmos: um para encontrar a rota de menor tempo entre dois pontos e outro para detectar se existe ponto isolado. Justifique escolhas e complexidades.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Representação: lista de adjacência ponderada (cada vértice guarda pares (vizinho, peso)), implementada com vetores ou dicionários para mapear ruas a vértices. Rota mais rápida: Dijkstra (para pesos = 0), complexidade O((V+E) log V) com heap de prioridade. Detectar isolamento: verificar para cada vértice se listas de saída e listas de entrada (ou graus) são vazias; custo O(V+E) para percorrer todas as listas. Justificativa: a lista é eficiente em espaço para grafos urbanos tipicamente esparsos e permite percursos e atualizações rápidas; algoritmos escolhidos são adequados para tempos positivos e análises locais.
Explicação
A representação em lista de adjacência é eficiente para grafos esparsos, como os encontrados em áreas urbanas, pois consome menos memória e permite acesso rápido aos vizinhos de cada vértice. O algoritmo de Dijkstra é apropriado para encontrar a rota de menor tempo em grafos com pesos não negativos, enquanto a verificação dos graus de entrada e saída permite identificar pontos isolados de forma simples e eficaz. Ambas as abordagens garantem uma análise rápida e eficiente das rotas e da conectividade do grafo.
Raio-X da questão
grafos direcionados com pesos
avaliacao
estruturas de dados · algoritmos de busca
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a representação de um grafo com uma lista de adjacência, não considerando a eficiência na busca de rotas.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Ao modelar rotas de ônibus de uma cidade em um algoritmo, qual estrutura de dados (registro, matriz, lista ou grafo) é…
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias…
- Elabore um algoritmo simples que utilize árvores ou grafos para resolver um problema cotidiano, como o planejamento de…
🔎 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