Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de decomposição e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices, construa a lista de adjacência; indique estruturas usadas e apresente a complexidade temporal e de espaço.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Inicialize um vetor/array adjacency de tamanho V, cada posição contém lista vazia. 2) Para cada aresta (u,v[,peso,id]) na edge list: append (v[,peso,id]) em adjacency[u]; se o grafo for não direcionado, append (u[,peso,id]) em adjacency[v]. 3) Se rótulos de vértice não forem 0..V-1, use um dicionário/map de rótulos?índice. Estruturas: vetor de listas (ou map de listas) e, opcionalmente, IDs por aresta. Complexidade: tempo O(V + E) para inicializar e percorrer arestas; espaço O(V + E) para a lista de adjacência (mais O(V) para metadados).
Explicação
A explicação apresenta um passo a passo claro para a construção da lista de adjacência a partir da edge list, utilizando estruturas adequadas como vetores ou dicionários. A complexidade temporal e de espaço é bem justificada, levando em consideração o número de vértices e arestas, o que é essencial para entender a eficiência do algoritmo. Além disso, menciona a necessidade de adaptar o índice dos vértices caso não sejam sequenciais, o que demonstra uma compreensão abrangente do problema.
Raio-X da questão
listas de adjacência
avaliacao
estruturas de dados · grafos e arestas
Revisar conceitos de grafos e suas representações.
O aluno pode confundir a representação de listas de adjacência com matrizes de adjacência, não utilizando a estrutura correta para a tarefa.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Ao decompor um algoritmo complexo, que documentação técnica mínima deve acompanhar cada função para permitir integração…
- Qual vantagem direta de transformar uma variável global em parâmetro de função ao decompor um algoritmo que manipula…
- Projete a decomposição de alto nível de um algoritmo que gera relatórios mensais de presença por aluno a partir de dados…
- Quais são, em ordem, as três etapas essenciais ao decompor um algoritmo complexo para facilitar sua resolução?
- Ao decompor um algoritmo que calcula estatísticas de temperatura, qual subtarefa trata de identificar e excluir outliers…
- Em um algoritmo que calcula a média de leituras de um sensor, ao aplicar decomposição, qual subtarefa deve preparar a…
Todas as questões de Estratégias de solução de problemas - Decomposição
🔎 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